= Solution
As a function of the independent edge indicators, the maximum matching number is unit-Lipschitz. The event $f(G)\geq 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,
$$
\mathbb P(f(G)\leq M-t)\leq2e^{-t^2/(4M)},
\qquad
\mathbb P(f(G)\geq M+t)\leq2e^{-t^2/[4(M+t)]}.
$$
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.
Back to article page
