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

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$.