In extremal graph theory, lower bounds for regularity lemmas are found by constructing graphs that require a large number of sets for a regular partition. Timothy Gowers created the first constructions in 1994 for the original Szemerédi regularity lemma to prove tower-type bounds for the lemma. The construction uses carefully chosen random subgraphs to build a graph which is not regular. Variations of Gowers’ construction prove tight bounds on different notions of regularity, and apply to regularity lemmas over other mathematical objects like hypergraphs.
Gowers’ construction was called a ‘tour de force’ by Béla Bollobás in his Fields Medal citation.