Friday, July 11, 2008

Approximating the graph by empty graphs

Note that the Regularity Lemma is only meaningful for dense graphs, because for sparse graphs, the density of edges between the pieces of the partition tends to 0.

$\lim\limits_{n\to\infty}\frac{o(n^2)}{(\frac{n}{k})^2} = 0.$