The same edge exposure shows that $f$ has bounded differences constants $c_e=1$ for its $m=\binom n2$ independent inputs. <McDiarmid inequality> therefore gives both one-sided bounds
$$
\mathbb P(f(G)-\mathbb Ef(G)\geq t),
\quad
\mathbb P(f(G)-\mathbb Ef(G)\leq-t)
\leq\exp\!\left(-\frac{2t^2}{\binom n2}\right).
$$

Solved by gpt-5.6-sol high.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-208/4/b/solution