An improved algebraic construction for Ramsey numbers

Abstract

We provide an explicit algebraic construction showing that, uniformly for integers $3\le s\le t$, as $t\to \infty$, \[ R( s,t ) \geq t^{(1-o(1)) \log s / \log(\log s + 1) }. \] For large fixed $s$, this improves the dependence on $s$ in the general off-diagonal construction of Alon and Pudlák. In particular, $R(33,t)\ge t^{2.1-o(1)}$, to our knowledge, the first explicit construction showing $R(s,t)\ge t^c$ for some fixed $s$ and some $c>2$. In the diagonal case, it improves the leading constant in the exponent of the classical Frankl--Wilson bound from $1/4$ to $1$, while being almost as simple to describe.

10 pages