Mathlib theorem · Existing formal mathematics
ProofAtlas

Existing in Mathlib · Combinatorics

Szemerédi’s Regularity Lemma

Given a finite simple graph, a positive tolerance ε, and a requested minimum l no larger than the vertex count, the vertices can be split into nearly equal-sized parts. The number of parts is at least l and no more than Mathlib’s source-defined bound, and all but an ε-proportion of ordered distinct part-pairs have stable edge density on sufficiently large subparts.

Exact theorem

Exact Mathlib statement

theorem szemeredi_regularity {α : Type*} [DecidableEq α] [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] {ε : ℝ} {l : ℕ} (hε : 0 < ε) (hl : l ≤ Fintype.card α) : ∃ P : Finpartition Finset.univ, P.IsEquipartition ∧ l ≤ #P.parts ∧ #P.parts ≤ SzemerediRegularity.bound ε l ∧ P.IsUniform G ε

The theorem at a glance

Szemerédi’s Regularity Lemma at a glance

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

A bounded energy-increment process yields an ε-uniform equipartition with l ≤ #parts(P) ≤ bound ε l. Explanatory diagram.
Detailed visual description

The poster leads with a finite simple graph divided into nearly equal cells, preserving a small minority of visibly irregular relations. Its central statement records ε > 0, l ≤ |V|, equipartition, the exact part-count inequalities, and ε-uniformity. Three source-bound movements refine non-uniformity witnesses, raise energy in controlled steps, and use energy ≤ 1 to force termination. The scope box explicitly excludes Szemerédi’s arithmetic-progression theorem and the unproved diagonal and degree versions.

Statement structure

Statement and scope

Statement map for Szemerédi’s Regularity LemmaEvery finite simple graph admits an ε-uniform equipartition whose number of parts lies between l and an explicit bound depending only on ε and l. Claim boundary: This page indexes Mathlib’s effective equipartition form of the finite graph regularity lemma. It assumes ε > 0 and l no larger than the finite vertex count, and it produces a partition of the full vertex set with part sizes differing by at most one, l ≤ #P.parts ≤ SzemerediRegularity.bound ε l, and at most an ε-proportion of ordered distinct part-pairs non-ε-uniform. It does not require every pair to be uniform. This is not Szemerédi’s theorem on arithmetic progressions, a diagonal or degree form of regularity, a counting or removal lemma, or a claim that the bound is optimal, small, or attained. The pinned upstream declaration is szemeredi_regularity. The complete formal statement is available in the Exact Mathlib statement section.Mathematical readingEvery finite simplegraph admits anε-uniform equipartitionwhose number of partslies between l and anexplicit bound dependingonly on ε and l.Claim boundaryThis page indexesMathlib’s effectiveequipartition form ofthe finite graphregularity lemma. Itassumes ε > 0 and l nolarger than the finitevertex count, and itproduces a partition ofthe full vertex set withpart sizes differing byat most one, l ≤#P.parts ≤SzemerediRegularity.boundε l, and at most anε-proportion of ordereddistinct part-pairsnon-ε-uniform. It doesnot require every pairto be uniform. This isnot Szemerédi’s theoremon arithmeticprogressions, a diagonalor degree form ofregularity, a countingor removal lemma, or aclaim that the bound isoptimal, small, orattained.Pinned declarationmathlib ·szemeredi_regularityStatement map for Szemerédi’s Regularity LemmaEvery finite simple graph admits an ε-uniform equipartition whose number of parts lies between l and an explicit bound depending only on ε and l. Claim boundary: This page indexes Mathlib’s effective equipartition form of the finite graph regularity lemma. It assumes ε > 0 and l no larger than the finite vertex count, and it produces a partition of the full vertex set with part sizes differing by at most one, l ≤ #P.parts ≤ SzemerediRegularity.bound ε l, and at most an ε-proportion of ordered distinct part-pairs non-ε-uniform. It does not require every pair to be uniform. This is not Szemerédi’s theorem on arithmetic progressions, a diagonal or degree form of regularity, a counting or removal lemma, or a claim that the bound is optimal, small, or attained. The pinned upstream declaration is szemeredi_regularity. The complete formal statement is available in the Exact Mathlib statement section.Mathematical readingEvery finite simplegraph admits anε-uniform equipartitionwhose number of partslies between l and anexplicit bound dependingonly on ε and l.Claim boundaryThis page indexesMathlib’s effectiveequipartition form ofthe finite graphregularity lemma. Itassumes ε > 0 and l nolarger than the finitevertex count, and itproduces a partition ofthe full vertex set withpart sizes differing byat most one, l ≤#P.parts ≤SzemerediRegularity.boundε l, and at most anε-proportion of ordereddistinct part-pairsnon-ε-uniform. It doesnot require every pairto be uniform. This isnot Szemerédi’s theoremon arithmeticprogressions, a diagonalor degree form ofregularity, a countingor removal lemma, or aclaim that the bound isoptimal, small, orattained.Pinned declarationmathlib ·szemeredi_regularity

Read the exact Mathlib declaration

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

Nested refinement preserves the vertices while a symmetric pair matrix classifies only distinct final part-pairs, mostly as regular. Explanatory scientific diagram.
Detailed visual description

The scientific schematic follows a finite vertex set through a coarse equipartition and a nested refinement. Its representative pair-classification matrix is symmetric for the undirected graph, leaves every diagonal cell neutral, and retains a small mirrored minority of irregular distinct-part pairs alongside an energy-increase motif.

Why it matters

A mathematical landmark

Szemerédi’s regularity lemma is a foundational structural result in extremal graph theory: every finite graph can be decomposed into a bounded number of nearly equal classes whose pairwise edge distributions are mostly random-like. Mathlib retains the effective equipartition endpoint together with the characteristic energy-increment proof architecture.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally
Locally reproducedExact upstream declaration replayed
Reviewed pageCurrent public presentation reviewed
Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

Claim boundary

No new theorem is claimed

This page indexes Mathlib’s effective equipartition form of the finite graph regularity lemma. It assumes ε > 0 and l no larger than the finite vertex count, and it produces a partition of the full vertex set with part sizes differing by at most one, l ≤ #P.parts ≤ SzemerediRegularity.bound ε l, and at most an ε-proportion of ordered distinct part-pairs non-ε-uniform. It does not require every pair to be uniform. This is not Szemerédi’s theorem on arithmetic progressions, a diagonal or degree form of regularity, a counting or removal lemma, or a claim that the bound is optimal, small, or attained.

Source and local evidence

Where the theorem comes from

Existing declaration
szemeredi_regularity in mathlib
Relationship
The checked artifact is the upstream declaration itself
Local Lean evidence
artifact.library.mathlib.szemeredi-regularity-lemma.v001
Source
Open the pinned upstream reference