The tail is cut for Ramsey numbers of cubes

The Ramsey number R(G) of a graph G is the least integer p such that for all bicolorings of the edges of the complete graph K_p, one of the monochromatic subgraphs contains a copy of G. We show that for any positive constant c and bipartite graph G=(U,V;E) of order n where the maximum degree of vertices in U is at most , . Moreover, we show that the Ramsey number of the cube Q_n of dimension n satisfies . In both cases, the small terms are removed from the powers in the upper bounds of a earlier result of the author.     

The Ramsey numbers of paths versus wheels

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let P_n denote a path of order n and W_m a wheel of order m+1. In this paper, we show that R(P_n,W_m)=2n-1 for m even and n?m-1?3 and R(P_n,W_m)=3n-2 for m odd and n?m-1?2.     

The Ramsey numbers of large cycles versus wheels

In this paper we show that the Ramsey number R(C_n,W_m)=2n-1 for even m and n?5m/2-1.     

Ramsey numbers of odd cycles versus larger even wheels

The generalized Ramsey number $R(G_1,G_2)$ is the smallest positive integer $N$ such that any red–blue coloring of the edges of the complete graph $K_N$ either contains a red copy of $G_1$ or a blue copy of $G_2$. Let $C_m$ denote a cycle of length $m$ and $W_n$ denote a wheel with $n+1$ vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers $R(C_{2k+1},W_n)$ of odd cycles versus larger wheels, leaving open the particular case where $n=2j$ is even and $k<j<3k∕2$. They conjectured that for these values of $j$ and $k$, $R(C_{2k+1},W_{2j})=4j+1$. In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that $R(C_{2k+1},W_{2j})\le 4j+334$. In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that $R(C_{2k+1},W_{2j})=4j+1$ if $j?k\ge 251$, $k<j<3k∕2$, and $j\ge 212299$.     

The Ramsey numbers for cycles versus wheels of odd order

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let C_n denote a cycle of order n and W_m a wheel of order m+1. It is conjectured by Surahmat, E.T. Baskoro and I. Tomescu that R(C_n,W_m)=2n−1 for even m≥4, n≥m and (n,m)≠(4,4). In this paper, we confirm the conjecture for n≥3m/2+1.     

Path-Star Ramsey numbers

Let f(m,n) be the least integer N such that for every graph G with N vertices, either G contains a path of m vertices or the complement of G contains a vertex of degree at least n. This paper determines f(m,n) for all m, n.     

Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr_∗(G,H) as the smallest integer k such that every 2-coloring of the edges of K_r−K_1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

The Ramsey numbers for cycles versus wheels of even order

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let C_n denote a cycle of order n and W_m a wheel of order m+1. Surahmat, Baskoro and Tomescu conjectured that R(C_n,W_m)=3n−2 for m odd, n≥m≥3 and (n,m)≠(3,3). In this paper, we confirm the conjecture for n≥20.     

Path-cycle Ramsey numbers

Recently, Ramsey numbers have been obtained for several classes of graphs. In particular, they have been studied for graphs of low order, pairs of paths, pairs of cycles, and for a star and a path. In this paper, the Ramsey numbers are obtained for all path-cycle pairs.     

Path-kipas Ramsey numbers

For two given graphs F and H, the Ramsey number R(F,H) is the smallest positive integer p such that for every graph G on p vertices the following holds: either G contains F as a subgraph or the complement of G contains H as a subgraph. In this paper, we study the Ramsey numbers , where P_n is a path on n vertices and is the graph obtained from the join of K₁ and P_m. We determine the exact values of for the following values of n and m: 1?n?5 and m?3; n?6 and (m is odd, 3?m?2n-1) or (m is even, 4?m?n+1); 6?n≤7 and m=2n-2 or m?2n; n?8 and m=2n-2 or m=2n or (q·n-2q+1?m?q·n-q+2 with 3?q?n-5) or m?(n-3)²; odd n?9 and (q·n-3q+1?m?q·n-2q with 3?q?(n-3)/2) or (q·n-q-n+4?m?q·n-2q with (n-1)/2?q?n-4). Moreover, we give lower bounds and upper bounds for for the other values of m and n.     

Path-fan Ramsey numbers

For two given graphs F and H, the Ramsey number R(F,H) is the smallest positive integer p such that for every graph G on p vertices the following holds: either G contains F as a subgraph or the complement of G contains H as a subgraph. In this paper, we study the Ramsey numbers R(P_n,F_m), where P_n is a path on n vertices and F_m is the graph obtained from m disjoint triangles by identifying precisely one vertex of every triangle (F_m is the join of K₁ and mK₂). We determine the exact values of R(P_n,F_m) for the following values of n and m: 1?n?5 and m?2; n?6 and 2?m?(n+1)/2; 6?n?7 and m?n-1; n?8 and n-1?m?n or ((q·n-2q+1)/2?m?(q·n-q+2)/2 with 3?q?n-5) or m?(n-3)²/2; odd n?9 and ((q·n-3q+1)/2?m?(q·n-2q)/2 with 3?q?(n-3)/2) or ((q·n-q-n+4)/2?m?(q·n-2q)/2 with (n-1)/2?q?n-5). Moreover, we give nontrivial lower bounds and upper bounds for R(P_n,F_m) for the other values of m and n.     

ContributionsChromatic Ramsey numbers

Suppose G is a graph. The chromatic Ramsey number r_c(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let M_n = min[r_c(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that M_n = (n − 1)² + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M₆ and M₇.     

Size bipartite Ramsey numbers

Let B, B₁ and B₂ be bipartite graphs, and let B→(B₁,B₂) signify that any red-blue edge-coloring of B contains either a red B₁ or a blue B₂. The size bipartite Ramsey number is defined as the minimum number of edges of a bipartite graph B such that B→(B₁,B₂). It is shown that is linear on n with m fixed, and is between c₁n²2ⁿ and c₂n³2ⁿ for some positive constants c₁ and c₂.     

Ramsey numbers for triples

Some recurrence inequalities for Ramsey numbers for triples are established by means of explicit constructions.     

On Ramsey numbers of fans

It is shown that r(F₂,F_n)=4n+1 for n≥2, and r(F_s,F_n)≤4n+2s for n≥s≥2.     

Some properties of Ramsey numbers

In this paper, some properties of Ramsey numbers are studied, and the following results are presented.

1. (1) For any positive integers k₁, k₂, …, k_m l₁, l₂, …, l_m (m> 1), we have

.

2. (2) For any positive integers k₁, k₂, …, k_m, l₁, l₂, …, l_n , we have

. Based on the known results of Ramsey numbers, some results of upper bounds and lower bounds of Ramsey numbers can be directly derived by those properties.

     

Another analog of Ramsey numbers

Mathematische Annalen -