In a recent preprint (Bradač 2026), Bradač proved a new lower bound for off-diagonal Ramsey numbers. For every fixed clique size , this lower bound has the same power of as the best known upper bound, missing it only by logarithmic factors.
Let denote the complete graph on vertices. In 1930, Ramsey (Ramsey 1930) proved that, for any positive integers and , there is an integer such that every red-blue colouring of the edges of contains either a red copy of or a blue copy of . The smallest such is denoted by and is called the two-colour Ramsey number.
Equivalently, is the smallest integer such that every graph on vertices contains either a clique of size or an independent set of size . This equivalent formulation is often the most useful one for lower bounds: to prove that , it is enough to construct a graph on vertices with no copy of and with independence number smaller than .
In previous blog posts, we have discussed upper bounds for Ramsey numbers in the diagonal case , as well as lower bounds in the case for a fixed constant . Here we turn to a different off-diagonal regime: is fixed, while .
Before the recent work of Bradač, the best general bounds available for fixed were where is a constant depending only on , and denotes a quantity tending to as . The lower and upper bounds in this general form are due to (Bohman and Keevash 2010) and (Li et al. 2001), respectively.
The case is exceptional, and much better understood. In that case becomes which determines the order of growth of up to a constant factor. The correct order of magnitude was established through the work of (Kim 1995; Ajtai et al. 1980; Shearer 1983). More recently, the constant in the lower bound was improved: one may take by the work of Hefty, Horn, King and Pfender (Hefty et al. 2025), and this value is conjectured to be optimal.
Already for , however, the general bound gives only leaving a gap in the power of . In 2024, Mattheus and Verstraete (Mattheus and Verstraete 2024) made a major breakthrough by proving a lower bound with the conjectured polynomial exponent.
Thus, for , the upper and lower bounds agree in the power of , differing only by a factor of order . The result of Mattheus and Verstraete was striking not just because it improved the numerical bound, but because it showed that the long-standing general lower-bound methods were not capturing the right polynomial behaviour.
Bradač’s new theorem extends this phenomenon to every fixed .
Combining Theorem with the upper bound in , we obtain In particular, for every fixed , the correct exponent of is now known to be . What remains open is the precise power of .
For , Bradač’s theorem is weaker than the best known bound. For , it recovers the Mattheus–Verstraete lower bound. Its new force begins at , where it closes the polynomial gap between the previously known lower bounds and the best known upper bounds.
The proof follows the broad strategy that has become increasingly important in modern Ramsey theory. One tries to build a dense graph with no , then show that it has few large independent sets, and finally pass to a suitable random subset to eliminate the remaining independent sets of size . Bradač’s construction is algebraic in origin and is based on polarity graphs coming from projective spaces. Although the resulting graphs are not pseudorandom in the strongest spectral sense, their independent sets can still be controlled efficiently, using ideas related to the container method.
A notable feature of the preprint is the role of AI in the final improvement. Bradač first obtained a weaker bound of the form The argument raising the power of from to the optimal was then found by an internal model at OpenAI, based on ideas from Bradač’s proof, and communicated to the author. The resulting theorem is one of the first high-profile examples in extremal combinatorics where an AI-derived mathematical argument appears as a decisive component in a research paper.
The main takeaway is simple: for fixed , the off-diagonal Ramsey number is now known to be After decades in which the polynomial exponent was known only in the triangle case and, more recently, in the case , Bradač’s theorem shows that the same exponent is correct for all fixed clique sizes.