The Szemerédi regularity lemma
ProvedFamousTheorems.szemeredi_regularity_lemmaThe Szemerédi regularity lemma. For every and every there is such that every finite graph with at least vertices has an equipartition of its vertex set into parts, , that is -uniform (all but at most an fraction of the pairs of parts are -regular).
The bound depends only on and , not on the graph. So every large graph is approximated, up to , by a bounded-size weighted "reduced" graph. The lemma is a central tool of extremal graph theory and additive combinatorics, used in the proofs of Szemerédi's theorem, the triangle removal lemma and the Erdős–Stone theorem.
Formalization note. Derived from Mathlib's szemeredi_regularity, whose explicit tower-type bound is SzemerediRegularity.bound ε l. Finpartition.IsEquipartition means the parts differ in size by at most one, and Finpartition.IsUniform G ε is Mathlib's notion of -uniform partition, based on SimpleGraph.IsUniform for pairs of parts. The quantification over all finite vertex types is uniform in the bound .
import Mathlib
namespace FamousTheorems
theorem szemeredi_regularity_lemma {ε : ℝ} (hε : 0 < ε) (l : ℕ) :
∃ M : ℕ, ∀ (α : Type*) [DecidableEq α] [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj],
l ≤ Fintype.card α → ∃ P : Finpartition (Finset.univ : Finset α),
P.IsEquipartition ∧ l ≤ P.parts.card ∧ P.parts.card ≤ M ∧ P.IsUniform G ε := by sorry
end FamousTheorems