The ith Ramsey number for matchings

The ith Ramsey number for matchings is determined. In addition, our results lead to the calculation of the Ramsey index for matchings.     

The Ramsey number for hypergraph cycles I

Let C_n denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v₁,…,v_n and edges v₁v₂v₃, v₃v₄v₅, v₅v₆v₇,…,v_n-1v_nv₁. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C_n, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible.     

The size Ramsey number

Let denote the class of all graphsG which satisfyG(G ₁,G ₂). As a way of measuring minimality for members of, we define thesize Ramsey number (G ₁,G ₂) by.We then investigate various questions concerned with the asymptotic behaviour of.     

On the Erd s-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings

A link between Ramsey numbers for stars and matchings and the Erd s-Ginzburg-Ziv theorem is established. Known results are generalized. Among other results we prove the following two theorems. Theorem 5. Let m be an even integer. If c : e (K_2m−1)→{0, 1,…, m−1} is a mapping of the edges of the complete graph on 2m−1 vertices into {0, 1,…, m−1}, then there exists a star K_1,m in K_2m−1 with edges e₁, e₂,…, e_m such that c(e₁)+c(e₂)++c(e_m)≡0 (mod m). Theorem 8. Let m be an integer. If c : e(K^r_(r+1)m−1)→{0, 1,…, m−1} is a mapping of all the r-subsets of an (r+1)m−1 element set S into {0, 1,…, m−1}, then there are m pairwise disjoint r-subsets Z₁, Z₂,…, Z_m of S such that c(Z₁)+c(Z₂)++c(Z_m)≡0 (mod m).     

Some multicolor bipartite Ramsey numbers involving cycles and a small number of colors

For bipartite graphs $G_1,G_2,\dots ,G_k$, the bipartite Ramsey number $b(G_1,G_2,\dots ,G_k)$ is the least positive integer $b$ so that any coloring of the edges of $K_{b,b}$ with $k$ colors will result in a copy of $G_i$ in the $i$th color for some $i$. In this paper, our main focus will be to bound the following numbers: $b(C_{2t_1},C_{2t_2})$ and $b(C_{2t_1},C_{2t_2},C_{2t_3})$ for all $t_i\ge 3,$$b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4})$ for $3\le t_i\le 9,$ and $b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4},C_{2t_5})$ for $3\le t_i\le 5.$ Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result.     

New upper bound for multicolor Ramsey number of odd cycles

Let $r_k\left(C_{2m+1}\right)$ be the $k$-color Ramsey number of an odd cycle $C_{2m+1}$ of length $2m+1$. It is shown that for each fixed $m\ge 2$, $r_k\left(C_{2m+1}\right)<c^k\sqrt{k!}$for all sufficiently large $k$, where $c=c\left(m\right)>0$ is a constant. This improves an old result by Bondy and Erd?s (1973).     

Remarks on the size Ramsey number of graphs

In this paper we prove that the cyclomatic number of a graph whose every 2-edgecolouring contains a monochromatic path witht edges is not less than 3t/4 ? 2. This fact leads to a simple non-probabilistic proof of the following theorem of Beck: $$\begin{array}{*{20}c} {lim inf{{\hat r\left( {P_t } \right)} \mathord{\left/ {\vphantom {{\hat r\left( {P_t } \right)} t}} \right. \kern-\nulldelimiterspace} t} \geqslant {9 \mathord{\left/ {\vphantom {9 4}} \right. \kern-\nulldelimiterspace} 4},} & {t \to \infty ,} \\ \end{array}$$ where \(\hat r(P_t )\) is the size Ramsey number of a pathP _t ont edges. We also show that the size Ramsey number of a (q + 1)-edge star with a tail of length one equals 4q ? 2, i.e., it is linear on the number of edges of the graph. Finally, we calculate that the upper bound for the size Ramsey number of a (q + 2)-edge star with a tail of length two is not greater than 5q + 3.     

Planar Ramsey numbers for cycles

For two given graphs G and H the planar Ramsey number PR(G,H) is the smallest integer n such that every planar graph F on n vertices either contains a copy of G or its complement contains a copy H. By studying the existence of subhamiltonian cycles in complements of sparse graphs, we determine all planar Ramsey numbers for pairs of cycles.     

On the Ramsey multiplicity for stars

In 1929, Ramsey proved a theorem guaranteeing that if G₁,G₂,…,G_k are graphs, then there exists an integer r so that if the edges of K_r are colored in any fashion with k colors a monochromatic G_i in color i exists for some i. Harary and Prins suggested the problem of deciding the minimum number of monochromatic G_i in any such coloring. It is the purpose of this paper to establish this minimum number in the case when G_i are stars for each i.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Gallai–Ramsey numbers for cycles

For given graphs G and H and an integer k, the Gallai–Ramsey number is defined to be the minimum integer n such that, in any k coloring of the edges of K_n, there exists a subgraph isomorphic to either a rainbow coloring of G or a monochromatic coloring of H. In this work, we consider Gallai–Ramsey numbers for the case when G=K₃ and H is a cycle of a fixed length.     

Degree Ramsey numbers for even cycles

Let $H\stackrel{s}{?}G$ denote that any $s$-coloring of $E\left(H\right)$ contains a monochromatic $G$. The degree Ramsey number of a graph $G$, denoted by $R_{\Delta }(G,s)$, is $min\{\Delta \left(H\right):H\stackrel{s}{?}G\}$. We consider degree Ramsey numbers where $G$ is a fixed even cycle. Kinnersley, Milans, and West showed that $R_{\Delta }(C_{2k},s)\ge 2s$, and Kang and Perarnau showed that $R_{\Delta }(C_4,s)=\Theta \left(s^2\right)$. Our main result is that $R_{\Delta }(C_6,s)=\Theta \left(s^{3∕2}\right)$ and $R_{\Delta }(C_{10},s)=\Theta \left(s^{5∕4}\right)$. Additionally, we substantially improve the lower bound for $R_{\Delta }(C_{2k},s)$ for general $k$.     

Perfect matchings extend to two or more hamiltonian cycles in hypercubes

Kreweras conjectured that every perfect matching of a hypercube $Q_n$ for $n\ge 2$ can be extended to a hamiltonian cycle of $Q_n$. Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of $Q_n$ for $n\ge 2$ can be extended to two or more hamiltonian cycles of $Q_n$. In this paper, we prove that every perfect matching of $Q_n$ for $n\ge 4$ can be extended to at least $2^{2^{n?4}}$ different hamiltonian cycles of $Q_n$.