Constructive lower bounds for off-diagonal Ramsey numbers (Q5935811): Difference between revisions

In this paper the authors combine techniques from several areas of mathematics to give a nice explicit construction for the classical Ramsey problem. It is shown that there is an \(\varepsilon>0\) such that for \(s\) fixed and \(m\) sufficiently large there is an explicit construction of a graph on at least \(m^{\varepsilon\sqrt{\log s/\log\log s}}\) vertices that does not contain a clique of size \(s\) or an independent set of size \(m\). In other words, \(R(s,m)=\Omega(m^{\varepsilon\sqrt{\log s/\log\log s}})\) for \(s\) fixed and \(m\to\infty\). Even though this constructive bound is weaker than the probabilistic lower bound showing that \(R(s,m)=\Omega(m^{s/2})\), the paper is very interesting due to the techniques used. At the heart of the construction are the norm graphs of \textit{J. Kollár, L. Rónyai} and \textit{T. Szabó} [Combinatorica 16, No. 3, 399-406 (1996; Zbl 0858.05061)]. To analyze their construction the authors use probabilistic and eigenvalue arguments, properties of pseudo-random graphs, a bound of Weil on character sums, as well as bounds on the Zarankiewicz problem and on the existence of \(\Delta\)-systems.