A note on pseudorandom Ramsey graphs (Q6192225): Difference between revisions

Summary: For fixed \(s \geq 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 \textit{T. Bohman} and \textit{P. Keevash} [Invent. Math. 181, No. 2, 291--336 (2010; Zbl 1223.05270)] from the random \(C_\ell\)-free process by polylogarithmic factors for all odd \(\ell \geq 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.