Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / A / 4

For nonempty disjoint vertex sets, the edge density is $d(X,Y)=e(X,Y)/(|X||Y|)$. A pair is $ϵ$-uniform, also called $ϵ$-regular, if every $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$ satisfiesIt says that restricting to reasonably large subsets does not noticeably change the edge density.

In the standard regularity-partition convention, the vertex sets form a disjoint partition, the nonexceptional sets $V_1,\dots ,V_k$ are nonempty and have a common size, $|V_0|<ϵ|V(G)|$, and at most $ϵk^2$ unordered nonexceptional pairs fail to be $ϵ$-uniform. One can instead use weak inequality for the exceptional-set bound without affecting the argument below once the size bound is strict. The exceptional set absorbs the rounding remainder when the graph order is not divisible by $k$.

Write $N=|G|$ and $D(U)=e(G[U])-p\left(\genfrac{}{}{0ex}{}{|U|}{2}\right)$. For disjoint sets $U,W$ of size at least ${ϵ}^{2}N$, the given identity and the corresponding binomial identity giveIn the nonvacuous regularity range $0<ϵ<1$, the original sets therefore satisfy $|d(X,Y)-p|<{ϵ}^3/3$. Their allowed subsets have size at least ${ϵ}^{2}N$, so $|d(X^{\prime },Y^{\prime })-p|<ϵ/3$. The triangle inequality givesThus the pair is uniform. For $ϵ\ge 1$, the definition is vacuous or immediate; the subsequent positive-integer condition $k<1/ϵ$ has no solutions.

For the partition deduction, choose $k$ equal classes of size $q=\lfloor N/k\rfloor$, putting the remainder into $V_0$. For fixed $k<1/ϵ$ and sufficiently large $N$, $q\ge ϵN$ and $|V_0|<k<ϵN$. Every class pair is uniform by what was just proved, which is stronger than the required condition. For example, it suffices thatA graph-size qualification is necessary if the printed deduction is read literally for every graph order. Under the standard nonempty-class definition, a one-vertex graph satisfies the discrepancy hypothesis for every $p$ and positive $ϵ$, but cannot be partitioned into two nonempty classes even when $2<1/ϵ$. The source omits this small-order qualification. If $k$ divides $N$, no rounding is needed and $N\ge k$ already suffices, since $N/k>ϵN$.