This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and my earlier selections, see this introductory post.
My choice for 2006 in Combinatorics is a theorem of David Conlon giving a dramatically improved upper bound for diagonal Ramsey numbers. His paper was first posted online in July 2006 and appeared in the Annals of Mathematics in 2009 (Conlon 2009).
Let denote the complete graph with vertices, that is, the graph in which every two distinct vertices are joined by an edge. In 1930, Ramsey (Ramsey 1930) proved that, for any positive integers and , there exists an integer such that every coloring of the edges of with two colors, red and blue, contains either a red or a blue . Here a red means a set of vertices such that all edges joining them are red, and similarly for a blue .
The smallest such integer is denoted by and called the Ramsey number. The numbers are called diagonal Ramsey numbers.
For example, This means that every red-blue coloring of the edges of contains a monochromatic triangle, but there exists a coloring of without one.
Determining the Ramsey numbers, or even estimating how rapidly they grow, is one of the central problems in combinatorics.
In 1935, Erdős and Szekeres (Erdős and Szekeres 1935) proved the upper bound where is the binomial coefficient. In particular, Using Stirling’s approximation for factorials, we have where means that as . Thus, the classical upper bound grows approximately as .
The proof of is surprisingly simple. Suppose that we have colored the edges of a sufficiently large complete graph red and blue, without creating a red or a blue . Choose any vertex . Its red neighbors cannot contain a red , since together with this would give a red . They cannot contain a blue either. Hence, has at most red neighbors.
Similarly, has at most blue neighbors. This implies and follows by induction.
Although elementary, the Erdős–Szekeres bound proved extremely difficult to improve substantially. In 1988, Thomason (Thomason 1988) obtained for some constant , where denotes the natural logarithm.
This was a significant improvement, but the factor gained over the Erdős–Szekeres bound was essentially only of order .
Conlon’s theorem introduced a much stronger saving.
The significance of this estimate is that the factor decreases faster than every fixed negative power of . Indeed, for every fixed positive integer , we have for all sufficiently large .
Consequently, Conlon’s theorem implies that, for every fixed , for all sufficiently large . This was a remarkable improvement over all earlier bounds.
Let us briefly discuss the proof. An edge coloring of a complete graph that contains neither a red nor a blue is called a Ramsey coloring. The Erdős–Szekeres argument bounds the number of red and blue edges incident to every vertex of such a coloring.
Thomason observed that one can obtain stronger restrictions by considering not only individual vertices, but also larger monochromatic complete subgraphs. For example, suppose that is a red complete subgraph with vertices. The vertices joined by red edges to every vertex of cannot contain a red , since this would create a red together with . They cannot contain a blue either. Thus, the number of such vertices is at most
Thomason used this observation to count monochromatic triangles and improve the classical bound.
Conlon extended the argument by counting monochromatic complete subgraphs of larger sizes. His key insight was that a hypothetical Ramsey coloring with too many vertices would have to be quasirandom: many of its statistical properties would resemble those of a graph in which each edge is independently colored red or blue with probability .
In particular, one would expect approximately red complete subgraphs on vertices, because each of their edges must be red.
On the other hand, the restrictions on how monochromatic complete subgraphs can be extended give upper bounds on their number. Conlon developed sufficiently precise estimates to show that these two requirements become incompatible if the graph has too many vertices. A careful induction then produces the saving in Theorem .
The result demonstrated the power of combining classical Ramsey-theoretic arguments with methods from the theory of quasirandom graphs.
Of course, Conlon’s theorem did not improve the base of the exponential upper bound. That breakthrough came much later. In 2023, Campos, Griffiths, Morris, and Sahasrabudhe announced a theorem, subsequently published in the Annals of Mathematics in 2026 (Campos et al. 2026), showing that for some constant and all sufficiently large . This was the first exponential improvement over the Erdős–Szekeres bound. We have discussed this result and its subsequent developments in an earlier blog post.
Although Conlon’s numerical bound has since been surpassed, his theorem remains an important milestone in Ramsey theory. It showed that information about the distribution of small monochromatic subgraphs can be combined with the classical inductive method to obtain savings far beyond those previously known. The resulting connection between Ramsey theory and quasirandomness has continued to play an important role in the subject.