= Solution
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.
Back to article page
