Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2009 / A / 3

For disjoint nonempty vertex sets, their edge density is $d(X,Y)=e(X,Y)/(|X||Y|)$. The pair is epsilon-regular or epsilon-uniform if for all $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$,It controls density on every sufficiently large subpair, rather than merely on average over chosen subpairs.

An epsilon-uniform partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering the vertex set, with $|V_0|\le ϵ|V(G)|$, equal nonexceptional class sizes $|V_1|=\cdots =|V_k|$, and at most $ϵk^2$ unordered pairs of distinct nonexceptional classes failing epsilon-uniformity. The exceptional set need not have the common size.

Szemerédi regularity lemma states that for every $ϵ>0$ and positive integer $m_0$, there is $M=M(ϵ,m_0)$ such that every sufficiently large finite graph, for example every graph of order at least $M$ after enlarging $M$ if needed, has such a partition with $m_0\le k\le M$. The bound depends only on the accuracy and minimum class count, not on the graph's order.

Let $S\subseteq X$ be the vertices with fewer than $dn/2$ neighbours in $Y$. If $|S|>ϵn$, its density to all of $Y$ is below $d/2$. But epsilon-uniformity applies to $(S,Y)$ and requiresa contradiction. Therefore $|S|\le ϵn$.

Apply part (c) to the pairs $(X_1,X_2)$ and $(X_1,X_3)$. Outside a union of at most $2ϵn$ exceptional vertices, every $v\in X_1$ has sets $Y=N(v)\cap X_2$ and $Z=N(v)\cap X_3$ of size at least $dn/2$.

These sets are large enough for epsilon-uniformity of $(X_2,X_3)$, because $d/2>ϵ$. HenceEvery such edge completes a distinct triangle through $v$. Thus at most $2ϵn$ vertices of $X_1$ fail the claimed triangle count. Summing these triangles over the good vertices counts each triangle with one vertex in each class exactly once. Since $d\le 1$ and $ϵ<d/4\le 1/4$,