Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 110 / 2

For disjoint nonempty vertex sets $A,B$, write $d(A,B)=e(A,B)/(|A||B|)$. The regular pair of vertex sets $(A,B)$ is $ϵ$-uniform when every $X\subseteq A$, $Y\subseteq B$ with $|X|\ge ϵ|A|$ and $|Y|\ge ϵ|B|$ satisfiesThis is also called an $ϵ$-regular pair.

Count transversal cliques by maintaining common neighbourhoods. For $r=1$ there are exactly $n$ copies, so the claim is immediate. For $r\ge 2$ the hypotheses are vacuous if $\lambda >1$; assume $0<\lambda \le 1$. SetAfter choosing vertices in the first $i-1$ classes, let $C_j\subseteq V_j$ be their common neighbours in each later class. We maintain $|C_j|\ge (\lambda -\eta {)}^{i-1}n\ge an$. In a regular pair, whenever $|C_j|\ge \eta n$, fewer than $\eta n$ vertices of $V_i$ have fewer than $(d(V_i,V_j)-\eta )|C_j|$ neighbours in $C_j$: otherwise those bad vertices, together with $C_j$, contradict regularity. There are at most $r-1$ future classes, so their union excludes at most $(r-1)\eta n$ candidates from $C_i$. At least $an/2$ choices remain, and each maintains the stated bound for all new common neighbourhoods.

Making these choices through all $r$ classes gives at least $(an/2{)}^r$ transversal cliques. Different selections give different vertex sets, since the classes are disjoint. ConsequentlyAll constants depend only on $r,\lambda$, not on $n$.

The Szemerédi regularity lemma states that for every $\eta >0$ and integer $m_0$ there exist $M,n_0$ such that every graph of order $N\ge n_0$ has a partition $V_0,V_1,\dots ,V_k$ with $m_0\le k\le M$, $|V_0|\le \eta N$, equal-sized nonexceptional classes, and at most $\eta k^2$ irregular unordered pairs of classes.

Apply the partition to prove clique removal. For $r\ge 2$, choose $\lambda =\min \{ϵ/4,1/2\}$, $m_0\ge \max \{r,4/ϵ\}$, and a regularity parameter $\eta \le \min \{ϵ/8,1/2\}$ small enough for the preceding counting argument at density $\lambda$. The Szemerédi regularity lemma supplies $M$. Delete all edges incident with $V_0$, inside individual classes, between irregular pairs, and between regular pairs with density below $\lambda$. If the common class size is $L$, the number deleted is at mostA surviving $K_r$ would have its vertices in distinct classes; every pair of these classes is regular and has density at least $\lambda$. The counting result would then give at least ${\delta }_0{L}^r$ copies in the original graph. Since $L=(N-|V_0|)/k\ge N/(2M)$, choose, for example,This would exceed $\delta N^r$, contradicting the assumed copy count. Thus fewer than $\delta N^r$ cliques can be destroyed by removing at most $ϵN^2$ edges, leaving no $K_r$. This is the clique removal lemma.

For $r=1$, take $\delta <1$: a graph of order $N$ always has $N$ copies of $K_1$, so the hypothesis is impossible. The assertion in that degenerate case is vacuous, rather than an edge-removal procedure capable of deleting vertices.