This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and earlier selections, see my introductory post.
My choice for 2005 in Combinatorics is Gowers’s effective version of the multidimensional Szemerédi theorem. The paper was submitted in 2005 and published in 2007 (Gowers 2007).
For a positive integer , write Szemerédi’s theorem states that, for every integer and real , there exists such that whenever , every subset with contains an arithmetic progression of length .
There is a remarkable multidimensional generalization. Let denote the set of integer vectors of length . For , a finite set , and an integer , write
Thus is a translated and uniformly enlarged copy of .
In 1978, Furstenberg and Katznelson (Furstenberg and Katznelson 1978) proved that, for every fixed , , and finite , every subset of a sufficiently large grid of density at least contains such a copy.
Ordinary Szemerédi’s theorem is the special case and
But may now be an arbitrary finite configuration: a triangle of lattice points, the vertices of a square, or a much more complicated multidimensional pattern.
The proof of Furstenberg and Katznelson used ergodic theory and was qualitative: it did not give an algorithm for determining how large has to be in terms of , , and .
Gowers changed this in 2005. Call explicitly computable if its value can, in principle, be obtained by a finite algorithm from the parameters. He proved (Gowers 2007):
This was also the first combinatorial proof of the multidimensional Szemerédi theorem. Gowers developed hypergraph analogues of Szemerédi’s regularity lemma and of the associated counting lemma. Roughly speaking, ordinary graphs are sufficient to encode three-term arithmetic progressions, while increasingly complicated configurations naturally lead to higher-uniformity hypergraphs. Independent hypergraph-regularity work of Nagle, Rödl, Schacht, and Skokan led to the same consequence (Rödl and Skokan 2004; Nagle et al. 2006).
The bounds supplied by these methods are enormous. Thus a natural next question is whether one can obtain reasonable quantitative bounds even for the simplest multidimensional patterns.
The first genuinely two-dimensional example is
A copy consists of
and is called a corner. Ajtai and Szemerédi had already proved in 1974 that every dense enough subset of contains a corner (Ajtai and Szemerédi 1974).
The quantitative problem asks how large a corner-free subset of can be. In 2006, Shkredov obtained the first “reasonable” bound, proving
for any and sufficiently large (Shkredov 2006).
For almost twenty years this remained essentially the state of the art. Then in 2025, Jaber, Liu, Lovett, Ostuni, and Sawhney obtained a dramatic improvement (Jaber et al. 2025):
for some absolute constant .
This is close in shape to the best possible bound. Behrend-type constructions give corner-free sets of size
for some constant . Thus the main remaining quantitative challenge is, roughly speaking, to improve the exponent towards .
The history is a good illustration of the difference between qualitative and quantitative combinatorics. Furstenberg and Katznelson proved that every dense multidimensional set must contain every fixed finite pattern. Gowers’s 2005 breakthrough made this statement effective by developing the hypergraph regularity machinery. Twenty years later, even for the tiny three-point corner, finding anything close to the correct quantitative bound remains a difficult and active problem.