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

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.