User:SunshineAllNight/sandbox3

Preliminaries

The Szemerédi regularity lemma requires the following definitions from graph theory.

Random graphs

Random graphs are an important class of graphs constructed using probability. In extremal graph theory, the main notion of random graphs is the Erdős–Rényi model G(n,p). The graph G(n,p) is constructed over n vertices and probability p that any two vertices will be connected by an edge. Average graphs from the Erdős–Rényi model can be thought as the most “uniform” compared to all graphs; therefore they have important properties that other graphs do not have.

One important property of G(n,p) is that the number of edges between two sets A, B in is $p|A||B|$, where $|A|$ is the number of vertices A contains. Another property is that we can calculate the number of subgraphs; for example, the number of triangle graphs $K_{3}$ is ${n \choose 3}p^{3}$ and more generally the number of complete graphs $K_{a}$ on $a$ vertices is ${n \choose a}p^{a \choose 2}$. The Szemerédi regularity lemma allows us to apply properties of random graph like these to arbitrary dense graphs.