Multicolor Ramsey numbers via pseudorandom graphs (Q2294097): Difference between revisions

Summary: A weakly optimal \(K_s\)-free \((n,d,\lambda)\)-graph is a \(d\)-regular \(K_s\)-free graph on \(n\) vertices with \(d=\Theta(n^{1-\alpha})\) and spectral expansion \(\lambda=\Theta(n^{1-(s-1)\alpha})\) for some fixed \(\alpha>0\). Such a graph is called optimal if additionally \(\alpha = \frac{1}{2s-3} \). We prove that if \(s_1,\ldots,s_k\ge3\) are fixed positive integers and weakly optimal \(K_{s_i}\)-free pseudorandom graphs exist for each \(1\le i\le k\), then the multicolor Ramsey numbers satisfy \[\Omega\Big(\frac{t^{S+1}}{\log^{2S}t}\Big)\le r(s_1,\ldots,s_k,t)\le O\Big(\frac{t^{S+1}}{\log^St}\Big),\] as \(t\rightarrow\infty \), where \(S=\sum_{i=1}^k(s_i-2)\). This generalizes previous results of \textit{D. Mubayi} and \textit{J. Verstraëte} [``A note on pseudorandom Ramsey graphs'', Preprint, \url{arXiv:1909.01461}], who proved the case \(k=1\), and \textit{N. Alon} and \textit{V. Rödl} [Combinatorica 25, No. 2, 125--141 (2005; Zbl 1090.05049)], who proved the case \(s_1=\cdots = s_k = 3\). Both previous results used the existence of optimal rather than weakly optimal \(K_{s_i}\)-free graphs.