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}$.     

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.     

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.     

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.     

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:

Ramsey Numbers for Trees II

Czechoslovak Mathematical Journal - Let r(G1, G2) be the Ramsey number of the two graphs G1 and G2. For n1 ? n2 ? 1 let S(n1, n2) be the double star given by $$Vleft( {Sleft(...     

Ramsey Numbers for Partially-Ordered Sets

We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains.     

On Pattern Ramsey Numbers of Graphs

A color pattern is a graph whose edges are partitioned into color classes. A family F of color patterns is a Ramsey family if there is some integer N such that every edge-coloring of K_N has a copy of some pattern in F. The smallest such N is the (pattern) Ramsey number R(F) of F. The classical Canonical Ramsey Theorem of Erdös and Rado [4] yields an easy characterization of the Ramsey families of color patterns. In this paper we determine R(F) for all families consisting of equipartitioned stars, and we prove that when F consists of a monochromatic star of size s and a polychromatic triangle.Acknowledgments. We thank the referees for pointing out several references where related results appeared.Project sponsored by the National Security Agency under Grant Number MDA904-03-1-0037. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.Final version received: January 9, 2004     

Poset Ramsey Numbers for Boolean Lattices

Order - For each positive integer n, let Qn denote the Boolean lattice of dimension n. For posets $P, P^{prime }$ , define the poset Ramsey number $R(P,P^{prime })$ to be the least N such that...