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

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.