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

For fixed disjoint $A,B$, the random variable $e(A,B)$ has the binomial distribution $\mathrm{Bin}(|A||B|,p)$. A two-sided Chernoff bound givesWhen $|A|,|B|\ge n/\log n$, this is at mostThere 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 mostwhich proves the simultaneous estimate.