Multicolor Ramsey numbers via pseudorandom graphs

Abstract

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,\dots ,s_k\ge 3$ 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 \[ Ω\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^{S}t}\Big), \] as $t\to \infty$, where $S={\sum }_{i=1}^k(s_i-2)$. This generalizes previous results of Mubayi and Verstraëte, who proved the case $k=1$, and Alon and Rödl, 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.

Cited by in corpus (1)

• Making an $H$-Free Graph $k$-Colorable