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

For disjoint nonempty vertex sets $A,B$, writeThe pair $(A,B)$ is a regular pair of vertex sets with parameter $ϵ$ ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge ϵ|A|$, and $|Y|\ge ϵ|B|$.

The Szemerédi regularity lemma says that for every $ϵ>0$ and $m_0$ there are $M,n_0$ such that every graph on at least $n_0$ vertices has a partitionwhere $m_0\le m\le M$, $|V_0|\le ϵ|V|$, the classes $V_1,\dots ,V_m$ have equal size, and all but at most $ϵm^2$ pairs $(V_i,V_j)$ are $ϵ$-uniform.

Because $\chi (H)=3$, every bipartite graph is $H$-free. The balanced complete bipartite graph therefore gives

For the reverse bound, fix $\delta >0$ and suppose that $G$ has more than $(1/2+\delta )\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges. Apply the Szemerédi regularity lemma with parameters much smaller than $\delta$. Form the reduced graph whose vertices are the regularity classes and whose edges are the regular pairs of density above a small fixed threshold. Edges inside classes, irregular pairs, and regular pairs below the threshold account for $o_{\delta }(n^2)$ edges. The remaining edges force the reduced graph to have more than $m^2/4$ edges.

By the Turan theorem, the reduced graph contains a triangle. The three corresponding regular pairs all have positive density, and the graph embedding lemma for regular pairs embeds every fixed three-colourable graph, in particular $H$, across suitable repeated subclusters of these three classes. Thus every sufficiently large graph of density above $1/2+\delta$ contains $H$. Letting $\delta \downarrow 0$ givesThis is the chromatic-number-three case of the Erdős-Stone theorem.

Let $R=R(C_5)$ be the fixed graph Ramsey number of the five-cycle. Partition $\lfloor n/R\rfloor R$ vertices into $\lfloor n/R\rfloor$ disjoint blocks of size $R$. For any one block, the probability that $G(n,1/2)$ induces a complete graph isThese events are independent for the disjoint blocks. Therefore the probability that none of them induces $K_R$ isWith probability tending to one, $G$ contains a copy of $K_R$. Every red-blue colouring of this copy contains a monochromatic $C_5$ by the definition of $R(C_5)$. Hence