Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 (Ramsey Theory on Graphs)

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

The uniform hypergraph Ramsey number $R^{(r)}(k)$ is the least $N$ such that every red-blue colouring of the $r$-element subsets of an $N$-element set contains a $k$-element set all of whose $r$-subsets have one colour.

Colour each triple of an $N$-element set independently and uniformly red or blue. For a fixed $k$-set, the probability of being monochromatic isThe expected number of monochromatic $k$-sets is thereforeTake $N=\lfloor 2^{c{k}^2}\rfloor$ with any sufficiently small absolute $c>0$. The exponent is negative for large $k$, since its leading terms are $c{k}^3-k^3/6$. Thus some colouring has no monochromatic $k$-set, proving

We use the Erdős-Rado selection argument. PutStarting with a sufficiently large reservoir, choose vertices $v_1,\dots ,v_m$ in order. After choosing $v_j$, successively halve the remaining reservoir for each $i<j$ so that the colour ofis constant as $x$ ranges over the final reservoir. The total number of halvings is at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$, so $2^{\left(\genfrac{}{}{0ex}{}{m}{2}\right)}+m$ initial vertices suffice.

Colour the pair $ij$, for $i<j<m$, by the stabilized colour of $\{v_i,v_j,v_{\ell }\}$ for $\ell >j$. Among $v_1,\dots ,v_{m-1}$, the definition of $R^{(2)}(k-1)$ gives a monochromatic set of $k-1$ vertices. Adjoining $v_m$ gives a monochromatic $k$-set for the original triple colouring. HenceThe binomial upper bound for a Ramsey number gives $R^{(2)}(k-1)<2^{2k}$, so the right-hand side is at mostfor an absolute $C>0$.

The blue hypergraph in the question is the three-edge hypergraph $K_4^{(3)-}$. The Erdős-Hajnal bound for the three-edge hypergraph on four vertices states that every $K_4^{(3)-}$-free three-uniform hypergraph on $N$ vertices has an independent set of size at leastIts proof exposes vertices successively and studies their link graphs. A blue triangle in a link is exactly a blue $K_4^{(3)-}$, so all links are triangle-free; applying the Shearer independence bound for a triangle-free graph in dyadic degree ranges either adds vertices to the independent set or leaves a reservoir whose logarithm decreases by only $O(\log \log N)$ per selected vertex. Iteration yields the displayed lower bound.

Now take $N=k^{Ck}$. For sufficiently large $C$,Thus, if there is no blue copy of $H$, the blue hypergraph has an independent $k$-set, which is a red $K_k^{(3)}$. Therefore

A set $R\subseteq V(G)$ is $(s,k)$-rich if every $s$-element subset of $R$ has at least $k$ common neighbours.

Choose $x_1,\dots ,x_t$ independently and uniformly from $V(G)$, with repetition, and putBy convexity,Let $Y$ count the $s$-subsets $S\subseteq W$ having fewer than $k$ common neighbours in $G$. For each such $S$,and thereforeDelete one vertex from every bad $s$-subset of $W$. The remaining set $R$ is $(s,k)$-rich and satisfies $|R|\ge |W|-Y$. The hypothesis givesso some choice has $|R|\ge r$.

Choose a bipartition $V(H)=A\bigsqcup B$ and inject $A$ into the $(d,k)$-rich set $R$. For each $b\in B$, the images of its neighbours form a set of at most $d$ vertices of $R$. Extend it, if necessary, to a $d$-element subset of $R$. Richness supplies at least $k$ common neighbours in $G$.

Embed the vertices of $B$ one at a time. At every step fewer than $k$ vertices have already been used, while at least $k$ common neighbours are available, so one unused choice remains. This greedy embedding preserves every edge of $H$ and proves

Let $N=\lceil k^{1+ϵ}\rceil$ and red-blue colour $K_N$. One colour class gives a graph $G$ withApply part (a) with $s=d$, the common-neighbour target equal to $k$, and an integerThe first term in its hypothesis is at least $c_1^{t}N$. The error term satisfiesSince $N/k=k^{ϵ}\to \infty$, the difference is at least $k$ for all sufficiently large $k$, depending only on $d$ and $ϵ$. Part (a) therefore gives a $(d,k)$-rich set of size at least $k$, and part (b) embeds $H$ in this colour. Hencefor sufficiently large $k$.

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