For fixed disjoint $A,B$, the random variable $e(A,B)$ has the <binomial distribution> $\operatorname{Bin}(|A||B|,p)$. A two-sided <Chernoff bound> gives
$$
\mathbb P\bigl(|e(A,B)-p|A||B||>\varepsilon|A||B|\bigr)
\leq2e^{-c_{p,\varepsilon}|A||B|}.
$$
When $|A|,|B|\geq n/\log n$, this is at most
$$
2\exp\left(-c_{p,\varepsilon}\frac{n^2}{(\log n)^2}\right).
$$
There are at most $3^n$ ordered disjoint pairs $(A,B)$, since each vertex can lie in $A$, in $B$, or in neither. The <union bound> therefore makes the probability of any failure at most
$$
2\cdot3^n\exp\left(-c_{p,\varepsilon}\frac{n^2}{(\log n)^2}\right)=o(1),
$$
which proves the simultaneous estimate.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 4 / c / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-122/4/c/solution