Multicolor Ramsey numbers via pseudorandom graphs

A weakly optimal Ks-free (n,d,λ)-graph is ad-regular Ks-free graph on n vertices with d= Θ(n1−α) and spectral expansion λ= Θ(n1−(s−1)α), for some fixed α >0. Such a graph is called optimal if additionally α=12s−3. We prove that if s1,...,sk>3 are fixed positive integers and weakly optimal Ksi-free pseudorandom graphs exist for each 1<i<k, then the multicolor Ramsey numbers satisfy Ω(tS+1log2St)6r(s1,...,sk,t)6O(tS+1logSt), as t→∞, where S=∑ki=1(si−2). This generalizes previous results of Mubayi andVerstraete, who proved the case k= 1, and Alon and Rodl, who proved the cases1=···=sk= 3. Both previous results used the existence of optimal rather than weakly optimal Ksi-free graphs