= Triangle-existence threshold in a binomial random graph
{title2=$p\asymp n^{-1}$}
If $np\to0$, the <triangle count in a binomial random graph> has <expectation> at most $(np)^3/6\to0$, so the <Markov inequality> shows there are no <triangles in a graph> with probability tending to one. If $np\to\infty$, the <triangle variance in a binomial random graph> divided by the squared mean is $O((np)^{-3})+O((n^2p)^{-1})\to0$. The <second moment method> then gives at least one <triangle in a graph> with probability tending to one. At the intermediate scale $np\to c\in(0,\infty)$, a nontrivial <Poisson limit for triangles in a binomial random graph> describes the count.
Back to article page
