The Szemeredi Regularity Lemma states that the vertex set of any sufficiently large graph can be partitioned into a bounded number of roughly equal parts such that the edges between almost every pair of parts behave, in a precise statistical sense, as if they were placed at random. Named for Endre Szemeredi, it is one of the most powerful tools of extremal graph theory, underlying proofs of numerous results including Szemeredi's own theorem on arithmetic progressions.
Facts
Partially Attested
Proof YearWikipedia dates the bipartite case used in Szemeredi's arithmetic progressions theorem to 1975 and the general graph version to 1978, this row records the general graph year. StatementFor every epsilon greater than 0 and positive integer m there exists an integer M such that if G is a graph with at least M vertices, there exists an integer k in the range m to M and an epsilon-regular partition of the vertex set of G into k sets. 1 Classification
Statement Form Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Szemeredi regularity lemma, Wikipedia
Proved By
Source Szemeredi regularity lemma, Wikipedia
Sources
1. Szemeredi regularity lemma, Wikipedia
Statement section
For every ε > 0 and positive integer m there exists an integer M such that if G is a graph with at least M vertices, there exists an integer k in the range m ≤ k ≤ M and an ε-regular partition of the vertex set of G into k sets.
History section
Endre Szemerédi proved the lemma over bipartite graphs for his theorem on arithmetic progressions in 1975 and for general graphs in 1978.
- In Branch: Graph Theory, Lead sentence
Proved By: Endre Szemeredi, Lead paragraph
In extremal graph theory, Szemerédi's regularity lemma states that a graph can be partitioned into a bounded number of parts so that the edges between parts
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.