A note on pseudorandom Ramsey graphs

Abstract

For fixed $s\ge 3$, we prove that if optimal $K_s$-free pseudorandom graphs exist, then the Ramsey number $r(s,t)$ is $t^{s-1+o(1)}$ as $t\to \infty$. Our method also improves the best lower bounds for $r(C_{\ell },t)$ obtained by Bohman and Keevash from the random $C_{\ell }$-free process by polylogarithmic factors for all odd $\ell \ge 5$ and $\ell \in \{6,10\}$. For $\ell =4$ it matches their lower bound from the $C_4$-free process.

We also prove, via a different approach, that $r(C_5,t)>(1+o(1))t^{11/8}$ and $r(C_7,t)>(1+o(1))t^{11/9}$. These improve the exponent of $t$ in the previous best results and appear to be the first examples of graphs $F$ with cycles for which such an improvement of the exponent for $r(F,t)$ is shown over the bounds given by the random $F$-free process and random graphs.