Multicolor Ramsey numbers for complete bipartite versus complete graphs (Q2922214)

The multicolor Ramsey number \(r(H_{1}, \ldots, H_{k})\) for graphs \(H_{1}, \ldots, 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 \leq i \leq k\). Ramsey's theorem [\textit{F. P. Ramsey}, Proc. Lond. Math. Soc. (2) 30, 264--286 (1929; JFM 55.0032.04)] states that \(r(K_{s}, K_{t}) < \infty\) for all \(s\) and \(t\). Determining these numbers or their asymptotic behavior is difficult. In this paper, the authors determine the asymptotic behavior of the multicolor Ramsey number \(r(K_{2,t}, \ldots, K_{2,t}, K_{m})\) up to a polylogarithmic factor for almost all ranges of \(t\) and \(m\). For the lower bounds, different constructions including random graphs and explicit graphs built from finite fields are used. To supply tight lower bounds, a technique of \textit{N. Alon} and \textit{V. Rödl} [Combinatorica 25, No. 2, 125--141 (2005; Zbl 1090.05049)] using a probabilistic method and spectral arguments is employed. The upper bound is a straightforward counting argument using the extremal number of \(K_{2,t}\). A sample result is NEWLINE\[NEWLINE c_{1} \frac{m^{2}t}{\log^{4}(mt)} \leq r(K_{2,t}, K_{2,t}, K_{m}) \leq c_{2} \frac{m^{2}t}{\log^{2}m} NEWLINE\]NEWLINE for any \(t\) and \(m\), where \(c_{1}\) and \(c_{2}\) are absolute constants.