A lower bound on the Ramsey number \(R_k(k+1,k+1)\)

One of the simplest mathematical statements is the Pigeonhole Principle: among \(km+1\) points colored with \(k\) colors, there exist \(m+1\) points with the same color. Ramsey’s Theorem extends the statement to colorings of pairs of point: for all positive integers \(k\) and \(n\), there exists an integer \(N\) such that for any coloring of pairs of \(N\) points with \(k\) colors, there exist \(n\) points such that all the pairs formed by these \(n\) points have the same color. Let \(R_k(n)\) be the smallest such integer \(N\).

Despite a long and rich history, asymptotic questions concerning the values of \(R_k(n)\) remain widely open. Even the case \(k=2\), where Erdős offered $250 for determining the limit \(\sqrt[n]{R_2(n)}\), remains widely open. Classical results in extremal combinatorics assert that \(2^{n/2+o(n)}\le R_2(n)\ge 4^{n+o(n)}\). A recent major breakthrough due to Campos, Griffiths, Morris and Sahasrabudhe decreased the base of the exponent in the upper bound below \(4\), which was subsequently refined to \(3.799\) by Gupta, Ndiaye, Norin and Wei.

This paper concerns lower bounds on \(R_k(n)\). A classical result of Erdős and Rado from 1953 gives a tower-type lower bound on \(R_k(n)\) when \(n\) is sufficiently large. The original proof of Erdős and Rado required \(n\) to be exponential in \(k\) and is based on the so-called stepping-up lemma. Recently, Conlon, Fox and Sudakov obtained a version of this lemma which allowed them to extend the range of \(n\) to all \(n\ge 5k/2+4\). The main result of the paper is a tower-type lower bound on \(R_k(k+1,k+1)\).