Szemerédi's Regularity Lemma (Q7361056)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Szemeredi_Regularity
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Szemerédi's Regularity Lemma |
AFP entry Szemeredi_Regularity |
Statements
5 November 2021
0 references
Chelsea Edmonds
0 references
Angeliki Koutsoukou-Argyraki
0 references
Lawrence C. Paulson
0 references
Szemerédi's Regularity Lemma (English)
0 references
Szemerédi's regularity lemma is a key result in the study of large graphs. It asserts the existence of an upper bound on the number of parts the vertices of a graph need to be partitioned into such that the edges between the parts are random in a certain sense. This bound depends only on the desired precision and not on the graph itself, in the spirit of Ramsey's theorem. The formalisation follows online course notes by Tim Gowers and Yufei Zhao .
0 references
