Szemerédi regularity lemma
Encyclopedia
In mathematics
, the Szemerédi regularity lemma states that every large enough graph
can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove Szemerédi's theorem
, and in he proved the full lemma. There are several extensions of the regularity lemma to hypergraphs, such as .
requires some definitions.
Let G be a graph.
The density of a pair of disjoint vertex
sets X, Y is the quantity
where E(X,Y) denotes the set of edges having one end vertex in X and one in Y.
For ε > 0, a pair of vertex sets X and Y is called ε-pseudo-random, if for all subsets A of X and B of Y satisfying
and 
, we have
A partition of the vertex set of G into k sets
is called an
ε-regular partition, if
for all i, j, and all except 
of the pairs 
, 
, i < j, are ε-pseudo-random.
The Regularity lemma states the following:
It is a common variant in the definition of an ε-regular partition to require that the vertex sets all have the same size, while collecting the leftover vertices in an "error"-set
whose size is at most an ε-fraction of the size of the vertex set of G.
The bound M for the number of parts in the partition of the graph given by the proofs of Szemeredi's regularity lemma is very large, given by a log(1/ε5)-level iterated exponential of m. At one time it was hoped that the true bound was much smaller, which would have had several useful applications. However
found examples of graphs for which M does indeed grow very fast and is at least as large as a log(1/ε)-level iterated exponential of m. In particular the best bound has level exactly 4 in the Grzegorczyk hierarchy
, and so is not an elementary recursive function.
, Sárközy
and Szemerédi
later proved in the blow-up lemma that the regular pairs in Szemerédi regularity lemma behave like complete bipartite graphs under the correct conditions. The lemma allowed for deeper exploration into the nature of embeddings of large sparse graphs into dense graphs.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Szemerédi regularity lemma states that every large enough graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove Szemerédi's theorem
Szemerédi's theorem
In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...
, and in he proved the full lemma. There are several extensions of the regularity lemma to hypergraphs, such as .
Formal statement of the regularity lemma
The formal statement of Szemerédi's regularity lemmaLemma (mathematics)
In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...
requires some definitions.
Let G be a graph.
The density of a pair of disjoint vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
sets X, Y is the quantity
where E(X,Y) denotes the set of edges having one end vertex in X and one in Y.
For ε > 0, a pair of vertex sets X and Y is called ε-pseudo-random, if for all subsets A of X and B of Y satisfying
and , we haveA partition of the vertex set of G into k sets
is called anε-regular partition, if
for all i, j, and all except of the pairs , , i < j, are ε-pseudo-random.The Regularity lemma states the following:
It is a common variant in the definition of an ε-regular partition to require that the vertex sets all have the same size, while collecting the leftover vertices in an "error"-set
whose size is at most an ε-fraction of the size of the vertex set of G.The bound M for the number of parts in the partition of the graph given by the proofs of Szemeredi's regularity lemma is very large, given by a log(1/ε5)-level iterated exponential of m. At one time it was hoped that the true bound was much smaller, which would have had several useful applications. However
found examples of graphs for which M does indeed grow very fast and is at least as large as a log(1/ε)-level iterated exponential of m. In particular the best bound has level exactly 4 in the Grzegorczyk hierarchy
Grzegorczyk hierarchy
The Grzegorczyk hierarchy , named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory . Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level...
, and so is not an elementary recursive function.
Extensions
KomlósJános Komlós (mathematician)
János Komlós is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy...
, Sárközy
Gábor N. Sárközy
Gábor N. Sárközy is a Hungarian-American Mathematician. Sárközy is a professor in the Computer Science Department at Worcester Polytechnic Institute, MA, United States and also a research fellow at the Computer and Automation Research Institute in the Hungarian Academy of Sciences...
and Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
later proved in the blow-up lemma that the regular pairs in Szemerédi regularity lemma behave like complete bipartite graphs under the correct conditions. The lemma allowed for deeper exploration into the nature of embeddings of large sparse graphs into dense graphs.