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

There are $m=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ independent edge indicators. Conditional on all indicators except one, changing that edge changes the maximum matching number by at most one. The conditional range is therefore at most one, so Popoviciu inequality on variances bounds each conditional variance by $1/4$. The tensorized conditional-variance inequality gives

Solved by gpt-5.6-sol high.

The same edge exposure shows that $f$ has bounded differences constants $c_e=1$ for its $m=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ independent inputs. McDiarmid inequality therefore gives both one-sided bounds

Solved by gpt-5.6-sol high.

Group the edge indicators into $n-1$ independent blocksAll edges in one block share vertex $i$. Replacing the entire block can change the maximum matching number by at most one: after deleting the at most one matched edge incident to $i$, a matching from either graph remains valid in the other. Applying McDiarmid inequality to these $n-1$ blocks gives

Solved by gpt-5.6-sol high.

Part (a) only gives a standard-deviation scale of order $n$, and part (b) gives the same concentration scale. Part (c) improves this to order $\sqrt{n}$. When $p=n^{-3/2}$, however, the mean itself is of order $\sqrt{n}$, so even part (c) does not show that fluctuations are little-$o$ of the mean. None of these bounds reveals the natural $n^{1/4}$ fluctuation scale obtained below.

Solved by gpt-5.6-sol high.

As a function of the independent edge indicators, the maximum matching number is unit-Lipschitz. The event $f(G)\ge k$ is certified by exhibiting the $k$ present edges of a matching, so $f$ is $g(k)=k$ certifiable. The Talagrand concentration inequality for certifiable functions around a median $M$ gives, for universal constants in the displayed standard version,Here $M\asymp \sqrt{n}$. If $t/n^{1/4}\to \infty$, then $t^2/(M+t)\to \infty$, as does $t^2/M$ whenever the corresponding event is possible. Both tail probabilities therefore tend to zero. Thus deviations of any order larger than $n^{1/4}$ are unlikely.

Solved by gpt-5.6-sol high.