Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 4

The graph Ramsey number $R(H)$ is the least $N$ such that every red-blue colouring of the edges of $K_N$ contains a monochromatic copy of $H$.

The minimum-degree Ramsey lower bound states that a graph of minimum degree $d$ admits an $H$-free colouring on every integer $N<2^{d/2}$. Its probabilistic proof colours edges independently and applies the local lemma to the events that a labelled copy of $H$ is monochromatic. Sincethe exponential cost $2^{1-e(H)}$ of a monochromatic copy dominates the number of compatible copies through every fixed edge. Hence such a colouring exists, and therefore

Solved by gpt-5.6-sol high.

Let $N=C{d}^{2d}k$ and red-blue colour $K_N$. Split its vertices into two classes of comparable size. At least half the cross-edges have one colour, say red. The bounded-degree bipartite Ramsey bound, proved by dependent random choice, gives a set $U$ in one class such that every subset of at most $d$ vertices of $U$ has at least $k$ common red neighbours in the other class.

Let $H=X\bigsqcup Y$ be a bipartition. Embed $X$ injectively into $U$. List the vertices of $Y$ and embed them one at a time. Each vertex of $Y$ has at most $d$ already embedded neighbours, whose common red neighbourhood has at least $k$ vertices; fewer than $k$ host vertices have yet been used, so a fresh choice is available. This greedily constructs a red copy of $H$. Thus

Solved by gpt-5.6-sol high.

The assertion as printed is false for unrestricted part sizes. Take $|A|=2$, let every vertex of $B$ be adjacent to one fixed vertex of $A$ and to no other vertex of $A$, and put $p=1/2$. The graph has $e(G)=p|A||B|$, but for $t=2$ the two distinct vertices of $A$ have no common neighbour, contradicting the claimed positive lower bound.

The corrected common-neighbourhood sampling bound, which is sufficient for the requested Ramsey consequence, assumes $|A|$ is sufficiently large compared with $t^2/p$. Indeed, averaging over uniformly chosen ordered distinct $x_1,\dots ,x_t\in A$ givesConvexity and ${\sum }_{y}d(y)\ge p|A||B|$ imply that this is at leastIf $|A|\ge 4t^2/p$, then $(1-(t-1)/(p|A|){)}^t\ge 1/2$, yielding the intended $p^t|B|/2$ bound with distinct vertices.

Now red-blue colour $K_N$, where $N=Ct{2}^t$, and split its vertices into equal parts $A,B$. One colour has cross-density at least $p=1/2$; call it red. Here $|A|\gg t^2$, so the corrected bound supplies $t$ vertices of $A$ having at leastcommon red neighbours when $C$ is large. Choosing any $t$ of those neighbours gives a red $K_{t,t}$. Hence

Solved by gpt-5.6-sol high.

Let $N=C(\log k)2^k$ and red-blue colour $K_N$. Across an equal bipartition, one colour has density at least $1/2$. Repeated common-neighbourhood sampling, withfinds distinct vertices $x_1,\dots ,x_t$ whose common neighbourhood in one colour has size at leastwhich is a sufficiently large polynomial in $k$ when $C_0$ is fixed and large.

Apply the complete-bipartite Ramsey completion lemma to this polynomial-size common neighbourhood. The lemma iterates the same averaging argument for the remaining $C_0\log k$ vertices: either they extend $x_1,\dots ,x_t$ to one side of a $K_{k,k}$ in the first colour, or their failed extensions have enough edges in the other colour to form a $K_{k,k}$ there. Taking $C_0$ and then $C$ sufficiently large therefore forces a monochromatic $K_{k,k}$. Consequently

Solved by gpt-5.6-sol high.