= Dense regular pair from edge surplus
{title2=$e(G)=n^2/6\Longrightarrow d(U,W)>1/4,\quad |U|=|W|\ge cn$}
The <Szemerédi regularity lemma> gives equal cells. If every regular cross-cell pair had density at most $1/4$, their total edge contribution would be at most $n^2/8$. Exceptional vertices, within-cell edges and irregular pairs contribute at most $(2\eta+1/(2m_0))n^2$. Choosing $\eta=1/100$ and $m_0=100$ contradicts $e(G)=n^2/6$. The dense pair is $1/8$-regular since it is already $\eta$-regular.
Back to article page
