Editing Extremal graph theory (section)

===Graph regularity===
{{main|Szemerédi regularity lemma}}

[[File:Epsilon regular partition.png|alt=regularity partition|thumb|200x200px|The edges between parts in a regular partition behave in a "random-like" fashion.]]

'''Szemerédi's regularity lemma''' states that all graphs are 'regular' in the following sense: the vertex set of any given graph can be partitioned into a bounded number of parts such that the bipartite graph between most pairs of parts behave like [[random graph|random bipartite graphs]].<ref name="pcm" />
This partition gives a structural approximation to the original graph, which reveals information about the properties of the original graph.

The regularity lemma is a central result in extremal graph theory, and also has numerous applications in the adjacent fields of [[additive combinatorics]] and [[computational complexity theory]]. In addition to (Szemerédi) regularity, closely related notions of graph regularity such as strong regularity and Frieze-Kannan weak regularity have also been studied, as well as extensions of regularity to [[hypergraphs]]. 

Applications of graph regularity often utilize forms of counting lemmas and removal lemmas. In simplest forms, the [[Graph removal lemma#graph counting lemma|graph counting lemma]] uses regularity between pairs of parts in a regular partition to approximate the number of subgraphs, and the [[graph removal lemma]] states that given a graph with few copies of a given subgraph, we can remove a small number of edges to eliminate all copies of the subgraph.

{{-}}