Let $X$ count the <triangles in a graph>[triangles] of the <binomial random graph> $G(n,p)$. Then
$$
\mu=\mathbb EX=\binom n3p^3=\Theta(n^3p^3).
$$
Two distinct triangle indicators are dependent only when the triangles share an edge. Hence their ordered <Janson dependency sum> is
$$
\Delta=\Theta(n^4p^5).
$$

If $0<p\leq n^{-1/2}$, then $\Delta=O(\mu)$. The first <Janson inequalities>[Janson inequality] gives
$$
\mathbb P(X=0)\leq e^{-\Omega(\mu)}.
$$
For the reverse bound, the events that individual triangles are absent are decreasing, so <Harris' inequality> gives
$$
\mathbb P(X=0)
\geq(1-p^3)^{\binom n3}
=e^{-O(n^3p^3)},
$$
where $p<1/2$ keeps the logarithmic estimate uniform. Thus the probability is $e^{-\Theta(p^3n^3)}$.

If $n^{-1/2}\leq p<1/2$, the extended Janson bound gives
$$
\mathbb P(X=0)
\leq
\exp\left(-\Omega\left(\frac{\mu^2}{\Delta}\right)\right)
=e^{-\Omega(pn^2)}.
$$
For a lower bound, fix a balanced bipartition of the vertices and require every edge inside either part to be absent. The resulting graph is <bipartite graph>[bipartite], hence <triangle-free graph>[triangle-free], and this event has probability
$$
(1-p)^{2\binom{\lfloor n/2\rfloor}{2}}
=e^{-O(pn^2)}.
$$
Combining the bounds proves the second regime.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 1 / b / Solution

 Solution

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