Public Mathlib landmark · existing upstream theorem · read-only
ProofAtlas

Combinatorics · existing Mathlib declaration

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.

The theorem at a glance

Szemerédi’s Regularity Lemma at a glance

A source-bound editorial overview of the exact Mathlib formulation. The image is explanatory; the statement map, formal type, and pinned source remain authoritative.

A bounded energy-increment process yields an ε-uniform equipartition with l ≤ #parts(P) ≤ bound ε l. Generated explanation only; the exact HTML statement and pinned source are authoritative.
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.

Formal orientation

Statement map

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. The pinned upstream declaration is szemeredi_regularity. The exact checked statement is 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 ε.Mathematical readingEvery finite simplegraph admits anε-uniform equipartitionwhose number of partslies between l and anexplicit bound dependingonly on ε and l.Pinned declarationmathlib ·szemeredi_regularityExact checked formtheoremszemeredi_regularity {α: Type*} [DecidableEq α][Fintype α] (G :SimpleGraph α)[DecidableRel G.Adj] {ε: ℝ} {l : ℕ} (hε : 0 <ε) (hl : l ≤Fintype.card α) : ∃ P :FinpartitionFinset.univ,P.IsEquipartition ∧ l ≤#P.parts ∧ #P.parts ≤SzemerediRegularity.boundε l ∧ P.IsUniform G ε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. The pinned upstream declaration is szemeredi_regularity. The exact checked statement is 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 ε.Mathematical readingEvery finite simplegraph admits anε-uniform equipartitionwhose number of partslies between l and anexplicit bound dependingonly on ε and l.Pinned declarationmathlib ·szemeredi_regularityExact checked formtheoremszemeredi_regularity {α: Type*} [DecidableEq α][Fintype α] (G :SimpleGraph α)[DecidableRel G.Adj] {ε: ℝ} {l : ℕ} (hε : 0 <ε) (hl : l ≤Fintype.card α) : ∃ P :FinpartitionFinset.univ,P.IsEquipartition ∧ l ≤#P.parts ∧ #P.parts ≤SzemerediRegularity.boundε l ∧ P.IsUniform G ε

This deterministic map orients the reader from the mathematical summary to the pinned declaration and exact checked form. The HTML statement below is authoritative.

Nested refinement preserves the vertices while making most final part-pairs regular. Scientific diagram · explanatory, not proof evidence.
Detailed visual description

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.

Complementary intuition

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.

The low-text schematic gives the theorem a visual identity; it does not replace the source-bound poster or exact statement.

Authoritative formal type

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 ε
Selected evidence declaration text
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 ε

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

These states distinguish upstream identity, local reproduction, review, and Atlas acceptance. This page is part of the public, read-only Mathlib landmark collection.

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.

Provenance

Origin and evidence stay separate

Existing declaration
szemeredi_regularity in mathlib
Relationship
The checked artifact is the upstream declaration itself
Preferred checked artifact
artifact.library.mathlib.szemeredi-regularity-lemma.v001
Source handling
Verified upstream reference; no mirrored source package