Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 1

Apply the Shearer independence bound for a triangle-free graph. It states that an $n$-vertex triangle-free graph of maximum degree at most $d$ has an independent set of sizefor an absolute $c>0$. The result is immediate for bounded $d$ after reducing $c$, while the theorem gives the asserted logarithmic gain for $d$ large. Thus

For completeness, the key input in Shearer's proof is to expose a random independent set one degree scale at a time. Triangle-freeness makes every neighbourhood independent, so conditioning on earlier choices creates no edges inside the available neighbours. The expected gain at degree scale $j$ is $\Omega (n_j/d)$; summing over the $\Theta (\log d)$ nonempty scales gives $\Omega (n\log d/d)$. The entropy, or hard-core-model, form of the argument makes this scale calculation rigorous without losing vertices counted at adjacent scales.

For every vertex $x$, the hypothesis $\Delta (G[N(x)])\le 1$ says that $G[N(x)]$ is a disjoint union of edges and isolated vertices. HenceThe locally sparse graph independence bound, with $f=2d$, now givesAs in part (a), bounded $d$ is absorbed by decreasing the absolute constant.

Let the blue edges form a graph $B$ on $N$ vertices, and suppose there is no blue copy of $H$. For every vertex $x$, the graph $B[N_B(x)]$ has maximum degree at most one. Indeed, if some $y\in N_B(x)$ had two neighbours $z,w$ inside $N_B(x)$, thenwould be the five blue edges of a copy of $H$.

Let $d=\Delta (B)$. If $d\ge 2k$, then a maximum-degree neighbourhood, being a matching plus isolated vertices, has an independent set of size at least $d/2\ge k$. This is a red $K_k$. We may therefore assume $d<2k$. Part (b) givesIf $d<\sqrt{k}$, the greedy independent-set bound gives $\alpha (B)\ge N/(d+1)>k$ once $N=C{k}^2/\log k$. If $\sqrt{k}\le d<2k$, then part (b) giveswhen $C$ is sufficiently large. In either case there is a red $K_k$, so