Some Bipartite Ramsey Numbers

Consider a complete bipartite graph K(s, s) with p = 2s points. Let each line of the graph have either red or blue colour. The smallest number p of points such that K(s, s) always contains red K(m, n) or blue K(m, n) is called bipartite Ramsey number denoted by rb(K(m, n), K(m, n)). In this paper, we show that

Ramsey Numbers of Some Bipartite Graphs Versus Complete Graphs

The Ramsey number r(H, K _n ) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,K_n) ￡ c_k,t [(n^1+1/k)/(ln^1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c _k,t is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359, 2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m ^γ ), where 1 < γ < 2. Then r(H,K_n) ￡ c_H ([(n)/(lnn)])^1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c _H is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000).     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

Multicolored Bipartite Ramsey Numbers of Large Cycles

For an integer r≥ 2 and bipartite graphs H_i,where 1 ≤i≤r,the bipartite Ramsey number br(H₁,H₂,…,H_r) is the minimum integer N such that any r-edge coloring of the complete bipartite graph K_N,N contains a monochromatic subgraph isomorphic to H_i in color i for some 1≤i≤r.We show that if ■     

Some tree-star Ramsey Numbers

The Ramsey Number r(G₁, G₂) is the least integer N such that for every graph G with N vertices, either G has the graph G₁ as a subgraph or $\text{G}$, the complement of G, has the graph G₂ as a subgraph.In this paper we embed the paths P_m in a much larger class $\text{T}$ of trees and then show how some evaluations by T. D. Parsons of Ramsey numbers r(P_m, K_1,n), where K_1,n is the star of degree n, are also valid for r(T_m, K_1,n) where T_m ∈ $\text{T}$.     

若干广义Ramsey数

本文讨论了关于树对完全图删去一些相交的三阶路的广义Ｒａｍｓｅｙ数Ｒ（Ｔ_ｍ，Ｋ_n－ｔＰ₃）和关路对完全图删去一些不相交的三阶完全图的广义Ｒａｍｓｅｙ数Ｒ（Ｐ_ｍ，Ｋ_n－ｔＫ₃），获得如下结果：1．如果m≥3,n≥3，那么Ｒ（Ｔ_ｍ，Ｋ_n－ｔＰ₃）=(m-1)(n-t-1)+1,0≤t≤[n/3].２．若m≥4,n,T≥1，则Ｒ（P_ｍ，Ｋ_n－ｔK₃）=(m-1)(n+2t-1)+1.从而，这两个结果部分地回答了１９８３年Ｒ．Ｊ．Ｇｏｕｌｄ和Ｍ．Ｓ．Ｊａｃｏｂｓｏｎ在［１］中提出的未解决问题．     

Bounds on Ramsey Numbers of Certain Complete Bipartite Graphs

Bounds on the Ramsey number r(K_l,m,K_l,n), where we may assume l ≤ m ≤ n, are determined for 3 ≤ l ≤ 5 and m ≈ n. Particularly, for m = n the general upper bound on r(K_l,n, K_l,n) due to Chung and Graham is improved for those l. Moreover, the behavior of r(K_3,m, K_3,n) is studied for m fixed and n sufficiently large.     

Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs

Let be graphs. The multicolor Ramsey number is the minimum integer r such that in every edge‐coloring of by k colors, there is a monochromatic copy of in color i for some . In this paper, we investigate the multicolor Ramsey number , determining the asymptotic behavior up to a polylogarithmic factor for almost all ranges of t and m. Several different constructions are used for the lower bounds, including the random graph and explicit graphs built from finite fields. A technique of Alon and Rödl using the probabilistic method and spectral arguments is employed to supply tight lower bounds. A sample result is for any t and m, where c₁ and c₂ are absolute constants.     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

Sharp Bounds For Some Multicolor Ramsey Numbers

Let H ₁,H ₂, . . .,H _k+1 be a sequence of k+1 finite, undirected, simple graphs. The (multicolored) Ramsey number r(H ₁,H ₂,...,H _k+1) is the minimum integer r such that in every edge-coloring of the complete graph on r vertices by k+1 colors, there is a monochromatic copy of H _i in color i for some 1ik+1. We describe a general technique that supplies tight lower bounds for several numbers r(H ₁,H ₂,...,H _k+1) when k2, and the last graph H _k+1 is the complete graph K _m on m vertices. This technique enables us to determine the asymptotic behaviour of these numbers, up to a polylogarithmic factor, in various cases. In particular we show that r(K ₃,K ₃,K _m ) = (m ³ poly logm), thus solving (in a strong form) a conjecture of Erdos and Sós raised in 1979. Another special case of our result implies that r(C ₄,C ₄,K _m ) = (m ² poly logm) and that r(C ₄,C ₄,C ₄,K _m ) = (m ²/log² m). The proofs combine combinatorial and probabilistic arguments with spectral techniques and certain estimates of character sums.* Research supported in part by a State of New Jersey grant, by a USA Israeli BSF grant and by a grant from the Israel Science Foundation. Research supported by NSF grant DMS 9704114.     

On Some Ramsey Numbers for Quadrilaterals Versus Wheels

For given graphs G ₁ and G ₂, the Ramsey number R(G ₁, G ₂) is the least integer n such that every 2-coloring of the edges of K _n contains a subgraph isomorphic to G ₁ in the first color or a subgraph isomorphic to G ₂ in the second color. Surahmat et al. proved that the Ramsey number ${R(C_4, W_n) \leq n + \lceil (n-1)/3\rceil}$ . By using asymptotic methods one can obtain the following property: ${R(C_4, W_n) \leq n + \sqrt{n}+o(1)}$ . In this paper we show that in fact ${R(C_4, W_n) \leq n + \sqrt{n-2}+1}$ for n ≥ 11. Moreover, by modification of the Erd?s-Rényi graph we obtain an exact value ${R(C_4, W_{q^2+1}) = q^2 + q + 1}$ with q ≥ 4 being a prime power. In addition, we provide exact values for Ramsey numbers R(C ₄, W _n ) for 14 ≤ n ≤ 17.     

Induced Ramsey Numbers

   We investigate the induced Ramsey number of pairs of graphs (G, H). This number is defined to be the smallest possible order of a graph Γ with the property that, whenever its edges are coloured red and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that, for any G and H with , we have

Ramsey数的几个新下界公式

本文通过构造循环图,得到并证明了公式:r(3,q)≥5(q-3)+2,r(3,q)≥7(q-5)+2,(q为奇数),又由所给引理:若r(l_1,k_1)>t_1,r(l_2,k_2)>t_2,则r(l_1-1·l_2-1+1,k_1-1·k_2-1+1)>t_1t_2,归纳出又一公式:r(3~n+1,3~n+1)≥17~n+1     

Canonical Pattern Ramsey Numbers

A color pattern is a graph whose edges have been partitioned into color classes. A family of color patterns is a Ramsey family provided there is some sufficiently large integer N such that in any edge coloring of the complete graph K_N there is an (isomorphic) copy of at least one of the patterns from . The smallest such N is the Ramsey number of the family . The classical Canonical Ramsey theorem of Erds and Rado asserts that the family of color patterns is a Ramsey family if it consists of monochromatic, rainbow (totally multicolored) and lexically colored complete graphs. In this paper we treat the asymmetric case by studying the Ramsey number of families containing a rainbow triangle, a lexically colored complete graph and a fixed arbitrary monochromatic graph. In particular we give asymptotically tight bounds for the Ramsey number of a family consisting of rainbow and monochromatic triangle and a lexically colored K_N. Among others, we prove some canonical Ramsey results for cycles.     

用拼图法研究Ramsey数下界的一些注记

指出论文《关于Ramsey数下界的部分结果》中的一些错误,评注用拼图法研究Ramsey数下界的一些困难问题,并提出两个猜想.     

On Geometric Graph Ramsey Numbers

For any two-colouring of the segments determined by 3n − 3 points in general position in the plane, either the first colour class contains a triangle, or there is a noncrossing cycle of length n in the second colour class, and this result is tight. We also give a series of more general estimates on off-diagonal geometric graph Ramsey numbers in the same spirit. Finally we investigate the existence of large noncrossing monochromatic matchings in multicoloured geometric graphs. Research partially supported by Hungarian Scientific Research Grants OTKA T043631 and NK67867.     

Three-Color Ramsey Numbers For Paths

We prove—for sufficiently large n—the following conjecture of Faudree and Schelp: