Multicolor Ramsey Numbers for Complete Bipartite Versus Complete Graphs

Abstract

Let H_1, ..., H_k be graphs. The multicolor Ramsey number r(H_1,...,H_k) is the minimum integer r such that in every edge-coloring of K_r by k colors, there is a monochromatic copy of H_i in color i for some 1 <= i <= k. In this paper, we investigate the multicolor Ramsey number $r(K_{2,t},...,K_{2,t},K_m)$, 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 $c_1{m}^{2}t/{\log }^4(mt)\le r(K_{2,t},K_{2,t},K_m)\le c_2{m}^{2}t/{\log }^{2}m$ for any t and m, where c_1 and c_2 are absolute constants.

24 pages, 0 figures

References in corpus (1)

• The early evolution of the H-free process