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.
Articles by others on the same topic
There are currently no matching articles.