Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 (Probabilistic Combinatorics)

Explore the connected component of a graph containing a fixed vertex $v$ by Breadth-first search. If the exploration discovers at least $m$ vertices, then before its $m$th discovery at least $m-1$ of at most $mn$ tested potential edges must be present. The tests are independent Bernoulli trials with parameter $p=(1-\epsilon )/n$, soThe binomial distribution on the right has mean $(1-\epsilon )m$. For $m\ge 2/\epsilon$, the exponential Markov bound givesfor an absolute constant $c>0$. The union bound over the $n$ choices of $v$ now givesTaking $m=C_{\epsilon }\log n$ with $C_{\epsilon }>2/(c{\epsilon }^2)$ makes this probability tend to zero. This proves the subcritical component bound for a binomial random graph.

Solved by gpt-5.6-sol high.

A connected graph on $s$ vertices containing at least two cycles has a spanning tree together with at least two further edges. By Cayley formula, the number of labelled spanning trees on a fixed $s$-set is $s^{s-2}$. Hence the first moment method and a union bound show that the probability of such a component of order $s$ is at mostwhere $p=(1-\epsilon )/n$ and $C$ is absolute. Requiring that the chosen set be a component would only add absent-edge conditions, so omitting them is a valid upper bound.

ThereforeThus every component in the stated range is either a tree or a unicyclic component with high probability.

Solved by gpt-5.6-sol high.

The sharp Hamilton cycle threshold for the Erdős-Rényi model says thatonly above the window $np=\log n+\log \log n+o(1)$. The hypothesis therefore places $p(n)$ above that window. The Hamiltonicity-to-pancyclicity sprinkling principle then says that three independent $G(n,p(n))$ rounds contain every cycle graph $C_{\ell }$, $3\le \ell \le n$, with high probability: one round supplies a Hamilton cycle, while the other two supply the chords and short-cycle edges used to obtain all intermediate lengths.

The union of the three rounds has individual edge probabilityBy the standard monotone coupling, it is a subgraph of $G(n,3p(n))$. Since being pancyclic is an increasing graph property, the required probability tends to one. If $3p(n)>1$, interpret the latter parameter as $\min \{3p(n),1\}$, in which case the conclusion is immediate.

Solved by gpt-5.6-sol high.

Letwhere the positive constant $c$ will be chosen small, and sample the binomial random graph $G(N,p)$. If $X$ counts its copies of $C_4$, thenIf $Y$ counts its independent $k$-sets, thenHere $pk\sim c^{-3/4}\log k$. Choosing $c$ sufficiently small makes the negative exponential term dominate $k\log (eN/k)$, so $\mathbb{E}Y=o(1)$. By Markov inequality, with positive probability $X<N/2$ and $Y=0$.

Starting from such a graph, delete one vertex from each remaining $C_4$. This random alteration method removes fewer than $N/2$ vertices, destroys every $C_4$, and cannot create an independent set of order $k$. The resulting graph has at least $N/2$ vertices, so its edges and nonedges give a red-blue colouring with neither a red $C_4$ nor a blue $K_k$. Consequently

Solved by gpt-5.6-sol high.

The Lopsided Lovász local lemma states that, for bad events $E_i$ with a lopsidependency graph, numbers $x_i\in [0,1)$ satisfyingimply $\mathbb{P}({\bigcap }_i{E}_i^c)>0$.

Fix any $0<\eta <1/6$, put $N=\lfloor k^{4/3+\eta }\rfloor$, and sample $G(N,p)$ withwhere $a>0$ is a sufficiently small absolute constant. Let $A_Q$ be the event that a specified copy $Q$ of $C_4$ is present, and let $B_S$ be the event that a specified $k$-set $S$ is independent. ThenFor product measures, the standard monotone-event lopsidependency graph joins an increasing event $A_Q$ to a decreasing event $B_S$ only when they use a common edge. Events of the same monotonicity need no lopsidependency edge. Thus each $A_Q$ has at most $4\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)$ neighbours of type $B$, and each $B_S$ has at most $C{k}^2{N}^2$ neighbours of type $A$.

Set $x_A=2p^4$ and $x_B=2q$. Sincewe haveOn the other side,whereas $-\log q\ge (a/3)k^2{N}^{-2/3}$. Choosing $a$ small makes both local-lemma inequalities hold. There is therefore a graph on $N$ vertices containing no $C_4$ and no independent $k$-set. Taking, for example, $\eta =1/12$ proves

Solved by gpt-5.6-sol high.

We use the following standard off-diagonal Ramsey result from the course: if $F$ is a forest on $h-1$ vertices and $K_1\vee F$ is obtained by adjoining a universal vertex, then, for $k$ sufficiently large in terms of $h$,Its proof combines the $r(K_3,K_k)=O(k^2/\log k)$ bound with an iterative neighbourhood embedding of the forest.

The graph $H_{\ell }$ in the question is exactly $K_1\vee P_{\ell -1}$, and a path is a tree, hence a forest. Substitution of $h=\ell$ givesas required.

Solved by gpt-5.6-sol high.

For disjoint nonempty vertex sets $X,Y$, their edge density of a bipartite graph isThe pair $(X,Y)$ is a $\epsilon$-regular pair ifwhenever $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$, $|X^{\prime }|\ge \epsilon |X|$, and $|Y^{\prime }|\ge \epsilon |Y|$. A partition $V_0,V_1,\dots ,V_m$ is equitable when $|V_1|=\cdots =|V_m|$; $V_0$ is its exceptional class.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and $m_0$ there are integers $M,n_0$ such that every graph on at least $n_0$ vertices has an equitable partitionwithfor which all but at most $\epsilon m^2$ pairs $(V_i,V_j)$, $1\le i<j\le m$, are $\epsilon$-regular.

Solved by gpt-5.6-sol high.

Apply the Szemerédi theorem with density $\epsilon$ and progression length five. For all sufficiently large $n$, the set $A$ contains a nonconstant five-term arithmetic progressionwhere $r\ne 0$. SetThese four elements and $e$ are distinct, and direct addition gives

Solved by gpt-5.6-sol high.

We prove the locally dense graph thinning lemma. Fix an integer $m>8/\epsilon$ and then choose $\delta <1/(3m)$. Partition the vertex set equitably as $V_1\bigsqcup \cdots \bigsqcup V_m$. For sufficiently large $n$, every part has at least $\delta n$ vertices. Consequently every pair $V_i,V_j$ has densityDelete all edges within parts. For each edge of $G$ joining $V_i$ to $V_j$, retain it independently with probability $p/d_{ij}$.

For fixed disjoint $A,B$, writing $A_i=A\cap V_i$ and $B_i=B\cap V_i$ givesThe omitted diagonal contribution satisfiesThe retained-edge indicators are independent. The exponential Markov bound therefore gives, for each fixed $(A,B)$,There are at most $3^n$ ordered pairs of disjoint vertex sets. A union bound shows that, with positive probability, no pair violates this estimate. For that realization,simultaneously for all disjoint $A,B$. As usual for a dense asymptotic statement, $n$ is taken sufficiently large; a lower-order integrality error is unavoidable for bounded $n$.

Solved by gpt-5.6-sol high.

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.