Triangle-existence threshold in a binomial random graph
ID: triangle-existence-threshold-in-a-binomial-random-graph
If , the triangle count in a binomial random graph has expectation at most , so the Markov inequality shows there are no triangles in a graph with probability tending to one. If , the triangle variance in a binomial random graph divided by the squared mean is . The second moment method then gives at least one triangle in a graph with probability tending to one. At the intermediate scale , a nontrivial Poisson limit for triangles in a binomial random graph describes the count.
New to topics? Read the docs here!