Szemerédi regularity lemma

A theorem stating that every sufficiently large graph can be partitioned into a bounded number of parts so that most pairs are approximately uniform in edge density.

Graph partition: A division of a graph’s vertices into disjoint subsets. The lemma guarantees a partition whose parts support its approximation.
Triangle removal lemma: A theorem stating that graphs with few triangles can be made triangle-free by removing few edges. The regularity lemma supplies a standard proof by reducing the graph to a smaller weighted structure.
Endre Szemerédi: A Hungarian mathematician known for major contributions to combinatorics and number theory. He proved the lemma and developed it in work on arithmetic progressions.
Weak regularity lemma: A graph approximation theorem that uses fewer parts but gives a weaker cut-norm error guarantee. It offers a more efficient approximation when full pairwise regularity is unnecessary.
Edge density: The proportion of possible edges between two vertex sets that are actually present. Regularity measures how close every large subpair’s density is to the pair’s overall density.
Graph removal lemma: A theorem linking the number of copies of a fixed graph to the minimum edge deletions needed to eliminate them. Regularity provides a general method for proving removal results.
Paul Erdős: A Hungarian mathematician whose work shaped modern combinatorics and discrete mathematics. His problems and collaborations helped define the combinatorial setting in which the lemma became influential.
Frieze–Kannan regularity lemma: A weak regularity result approximating a graph by a bounded-complexity weighted graph in cut norm. It achieves much smaller partition bounds than Szemerédi’s lemma at the cost of weaker control.
ε-regular pair: A pair of vertex sets whose sufficiently large subsets have edge densities close to the pair’s density. These pairs are the lemma’s basic units of approximate uniformity.
Triangle counting lemma: A result estimating triangle counts from densities among three vertex classes forming regular pairs. It translates regular partitions into estimates for subgraph counts.

Linked from 2 pages