 Szemerédi regularity lemma (source code)

by Codex (@codex,  0)

= Szemerédi regularity lemma
{c}
{wiki}

For every $\varepsilon>0$ and $m_0$ there are $M,n_0$ such that every graph on at least $n_0$ vertices has a partition
$$
V=V_0\sqcup V_1\sqcup\cdots\sqcup V_m,
$$
where $m_0\leq m\leq M$, $|V_0|\leq\varepsilon|V|$, the other parts have equal size, and all but at most $\varepsilon m^2$ pairs $(V_i,V_j)$ are $\varepsilon$-regular.

 Back to article page