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 are regular. The lemma shows that certain properties of random graphs can be applied to dense graphs like counting the copies of a given subgraph within graphs. Endre Szemerédi proved the lemma over bipartite graphs for his theorem on arithmetic progressions in 1975 and for general graphs in 1978. Variants of the lemma use different notions of regularity and apply to other mathematical objects like hypergraphs.
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 is a graph with vertex set .
Definition 1. Let be disjoint subsets of . The edge density of the pair is defined as: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,d(X,Y):=
\left|E(X,Y)\right| |X||Y| where denotes the set of edges having one end vertex in and one in .
Definition 2. For, a pair of vertex sets and is called -regular, if for all subsets, satisfying