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!