Ramsey theorems for multiple copies of graphs

Source abstract

If G G and H H are graphs, define the Ramsey number r ( G , H ) r(G,H) to be the least number p p such that if the edges of the complete graph K p {K_p} are colored red and blue (say), either the red graph contains G G as a subgraph or the blue graph contains H H . Let m G mG denote the union of m m disjoint copies of G G . The following result is proved: Let G G and H H have k k and l l points respectively and have point independence numbers of i i and j j respectively. Then N − 1 ⩽ r ( m G , n H ) ⩽ N + C N - 1 \leqslant r(mG,nH) \leqslant N + C , where N = k m + l n − m i n ( m i , m j ) N = km + ln - min(mi,mj) and where C C is an effectively computable function of G G and H H . The method used permits exact evaluation of r ( m G , n H ) r(mG,nH) for various choices of G G and H H , especially when m = n m = n or G = H G = H . In particular, r ( m K 3 , n K 3 ) = 3 m + 2 n r(m{K_3},n{K_3}) = 3m + 2n when m ⩾ n , m ⩾ 2 m \geqslant n,m \geqslant 2 .