page_title: Szemerédi regularity lemma
section_title: Statement
hierarchical_section_title: Szemerédi regularity lemma / Statement
caption_attribution_description: English: Diagram of epsilon regular pair
context_page_description: Szemerédi's regularity lemma is one of the most powerful tools in extremal graph theory, particularly in the study of large dense graphs. It states that the vertices of every large enough graph can be partitioned into a bounded number of parts so that the edges between different parts behave almost randomly.
  According to the lemma, no matter how large a graph is, we can approximate it with the edge densities between a bounded number of parts. Between any two parts, the distribution of edges will be pseudorandom as per the edge density. These approximations provide essentially correct values for various properties of the graph, such as the number of embedded copies of a given subgraph or the number of edge deletions required to remove all copies of some subgraph.
context_section_description: To state Szemerédi's regularity lemma formally, we must formalize what the edge distribution between parts behaving 'almost randomly' really means. By 'almost random', we're referring to a notion called ε-regularity. To understand what this means, we first state some definitions. In what follows G is a graph with vertex set V.
  Definition 1. Let X, Y be disjoint subsets of V. The edge density of the pair (X, Y) is defined as:
  
  where E(X, Y) denotes the set of edges having one end vertex in X and one in Y.
  We call a pair of parts ε-regular if, whenever you take a large subset of each part, their edge density isn't too far off the edge density of the pair of parts. Formally,
  Definition 2. For ε > 0, a pair of vertex sets X and Y is called ε-regular, if for all subsets A ⊆ X, B ⊆ Y satisfying |A| ≥ ε|X|, |B| ≥ ε|Y|, we have
  The natural way to define an ε-regular partition should be one where each pair of parts is ε-regular. However, some graphs, such as the half graphs, require many pairs of partitions (but a small fraction of all pairs) to be irregular. So we shall define ε-regular partitions to be one where most pairs of parts are ε-regular.
  Definition 3. A partition of  into  sets  is called an -regular partition if
  Now we can state the lemma:
  Szemerédi's Regularity Lemma. 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.
  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 O(ε⁻⁵)-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 Gowers (1997) found examples of graphs for  which M does indeed grow very fast and is at least as large as a ε-1/16-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.
caption: Subset pairs of a regular pair are similar in edge density to the original pair.
exif: {}