Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 9 / 4

We use the following precise form of the Szemerédi regularity lemma. For every $0<\eta <1/2$ and positive integer $m_0$, there are integers $M,n_0$ such that every graph on $n\ge n_0$ vertices has a partitionwith at most $\eta k^2$ irregular unordered pairs among the nonexceptional classes. Here $d(A,B)=e(A,B)/(|A||B|)$ for disjoint nonempty sets, and $(A,B)$ is an $\eta$-regular pair ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \eta |A|$, $|Y|\ge \eta |B|$.

For the proof, let $f(x,y)$ be the adjacency indicator, including $f(x,x)=0$, and define $d(A,B)$ by averaging $f$ on $A\times B$ even for diagonal cells. The regularity energy of a partition $\mathcal{P}$ isEvery exceptional vertex is represented by its own singleton cell in this energy. If a rectangle $A\times B$ is refined into smaller rectangles with densities $d_{ij}$ and weights $w_{ij}=|A_i||B_j|$, expanding the square gives the refinement variance identity for regularity energyThus refinement never decreases energy.

Suppose an equitable partition with $k$ classes of size $L$ fails the desired conclusion. For every irregular pair choose witness subsets $X\subseteq V_i$, $Y\subseteq V_j$, each of size at least $\eta L$, whose density differs from $d(V_i,V_j)$ by more than $\eta$. Split each class by all witness subsets involving it. Each class has at most $2^{k-1}$ atoms. On a witness rectangle, the weighted mean of $d_{ab}-d(V_i,V_j)$ is $d(X,Y)-d(V_i,V_j)$. The Cauchy-Schwarz inequality therefore bounds the energy increment on this rectangle below byThe different original cell pairs have disjoint rectangles. More than $\eta k^2$ irregular unordered pairs, with both orientations counted in the energy, thus increase it by more than $2{\eta }^5{k}^2{L}^2/n^2$. As long as $|V_0|\le \eta n<n/2$, this is greater than ${\eta }^5/2$, and in particular greater than ${\eta }^5/4$.

Restore equitability by dividing each atom into pieces of common size $\ell =\lfloor L/4^k\rfloor$, moving each leftover vertex into the exceptional set as a singleton energy cell. This remains a refinement, so the energy gain persists. There are at most $k{2}^k$ atoms, so the additional exceptional vertices number at mostIf $L\ge 2\cdot 4^k$, then $\ell \ge L/(2\cdot 4^k)$, and the new number $k^{\prime }$ of equal cells satisfies $k\le k^{\prime }\le 4k{4}^k$. For the lower bound, within each old class the leftover count is at most $2^k\ell <L$, so at least one full new cell survives. For the upper bound, $n/\ell \le 2(n/L)4^k\le 4k{4}^k$, using $kL\ge n/2$. This proves equalization with a controlled exceptional set without any energy loss.

Put $T=\lceil 4{\eta }^{-5}\rceil +1$. Choose $k_0\ge m_0$ with $T{2}^{-k_0}\le \eta /2$. Start with $k_0$ equal classes and fewer than $k_0$ exceptional vertices. Iterate the bounded recurrence $k\mapsto 4k{4}^k$ $T$ times to obtain a bound $M$. Choose $n_0$ so large that the initial remainder is at most $\eta n/2$ and, for every $k\le M$, $(1-\eta )n/k\ge 2\cdot 4^k$. The total exceptional set remains at most $\eta n$, since at most $T$ rounds each add at most $n{2}^{-k_0}$. Each failing round raises an energy in $[0,1]$ by more than ${\eta }^5/4$, so fewer than $T$ rounds can fail. This proves the lemma with all constants independent of the input graph.

For the application, write $h=|V(F)|$ and $\chi (F)=r+1$. We may replace the given tolerance by a smaller one, so assume $0<\epsilon <1$. Set $d=\epsilon /4$, take $m_0\ge 8/\epsilon$, and chooseApply the lemma and delete all edges incident with $V_0$, all edges inside a class, all edges across irregular pairs, and all edges across regular pairs of density below $d$. The resulting spanning subgraph $H$ loses at mostLet $R$ be the reduced graph of a regularity partition, whose edges represent the surviving regular pairs of density at least $d$. We show that a copy of $K_{r+1}$ in $R$ forces a copy of $F$ in $G$.

Choose a proper $(r+1)$-coloring of $F$ and assign its color classes to the corresponding clusters. Embed its vertices one at a time. For each unembedded vertex maintain the candidate set in its cluster consisting of unused vertices adjacent to all already embedded neighbours. After at most $h$ restrictions its size is at least $(d-\eta {)}^{h}L-h\ge (d/2{)}^{h}L-h$. This last quantity is at least $2h\eta L$ when $L$ is large, so every such candidate set is large enough for regularity. In an $\eta$-regular pair of density $p\ge d$, fewer than $\eta L$ vertices on one side have fewer than $(p-\eta )|Y|$ neighbours in any fixed set $Y$ on the other side of size at least $\eta L$: otherwise these vertices and $Y$ violate regularity. For the vertex currently being embedded, there are at most $h$ relevant future candidate sets. At most $h\eta L$ vertices are bad for one of them. Its own candidate set has at least $2h\eta L$ vertices, so an unused good vertex can be chosen. All future candidate sets shrink by at most the factor $d-\eta$, apart from the removal of a used vertex; the stated size bound follows inductively, since the accumulated removals are at most $h$. This completes the graph embedding lemma for regular pairs in the form needed here.

Since $G$ is $F$-free, $R$ is $K_{r+1}$-free. Any $K_{r+1}$ in $H$ would use distinct clusters, because intraclass edges were deleted, and project to a $K_{r+1}$ in $R$. ThereforeThe required threshold on $n$ depends only on $F$ and $\epsilon$, since $k\le M$ makes every nonexceptional cluster sufficiently large.