For fixed , a binomial random graph has no -cliques with probability tending to one if , and has at least one with probability tending to one if . The first assertion uses the first moment method. The second uses the overlap formula for the variance of a clique count: overlapping -sets with contribute , and each contribution tends to zero above this threshold. The fixed-size qualification matters.
Write and . The first mean condition implies eventually. For , this yields , and each fixed- term tends to zero when . The second mean condition implies eventually. Writing gives for , and . Both bounding series are summable. The overlap formula for the variance of a clique count therefore gives relative variance tending to zero; the second moment method proves an -clique exists with high probability.
Let count -cliques, and put . Since , the Markov inequality gives . Any larger clique contains an -clique, so it remains to prove with high probability.
We give the required growing-clique overlap bound explicitly. Set and, for ,
The quantity is the probability that a uniformly chosen -set overlaps a fixed -set in exactly vertices. Two clique indicators share exactly edge requirements, so their joint-to-product ratio is . Overlap zero or one gives independence. Hence the overlap formula for the variance of a clique count implies
We must bound this sum with allowed to grow.
Eventually and . Using , these inequalities give
For , a union bound over the selected shared vertices gives . Put . Since and ,
For each fixed , the first bound tends to zero if stays bounded, because its power of is negative. If , the middle bound tends to zero because . Thus each fixed- term tends to zero along arbitrary admissible sequences. The bounding series converges. Splitting at a fixed large index, then taking and the index to infinity, proves that the entire lower-half sum is .
For the upper half write . The exact diagonal comparison is
For , the second bound on gives
The last inequality uses : the exponent of in the bracket is negative, so substituting bounds it above. Uniformly for this range of , . Indeed , and concavity of , checked at and , gives . It follows that
Thus . The second moment method gives . Combining this with the absence of larger cliques proves
The restriction on is used in both overlap ranges; divergence of a clique count in a binomial random graph alone would not suffice for arbitrary growing .
Expand , where the sum is over ordered pairs of -sets. If , the two cliques together require different edges: precisely the edges within the overlap are counted twice. Therefore
There are choices of , then ways to choose the overlap and ways to choose the remaining vertices of . It follows that
A binomial coefficient is zero when its lower argument is outside its possible range. The term includes and equals , as it should.
Now take the usual fixed- interpretation of the appearance assertion. For , deterministically. For fixed , the assumption gives
since . Eventually . Subtracting in the second-moment formula, and using the identity that the overlap counts sum to the total number of ordered pairs, gives the overlap formula for the variance of a clique count:
Overlaps of zero or one vertex have no shared edge and hence independent indicators, so their contributions vanish. For fixed , the combinatorial coefficient in the -th summand is . Moreover, because and ,
There are only finitely many terms. Thus . The Chebyshev inequality then gives
proving the fixed-size clique appearance threshold:
The fixed-size condition cannot simply be dropped. For and ,
However the complement graph has a binomial number of missing edges with mean asymptotic to and variance at most that mean. By the Chebyshev inequality, . Conditional on , choose two distinct missing edges uniformly; their endpoints are disjoint except with probability
Thus with probability tending to one the complement has two disjoint edges. Deleting one vertex cannot remove both, so no -clique exists. In this example , despite . This is growing clique size can invalidate a first-moment appearance criterion; the exact second-moment identity remains valid for growing , but the stated conclusion needs the conventional fixed- quantifier.
Let count the copies of the complete graph in the binomial random graph . By linearity of the expected value and independence of distinct edges,
Throughout, is sufficiently large that . We have , and .
First, since ,
The first moment method proves .
For the existence of a -clique, put and . Since ,
This alone is insufficient: we must control the variance via the overlap formula for the variance of a clique count. Let indicate that a given -set spans a clique. If , the two copies share edges, so
For their edge sets are disjoint and the covariance vanishes, even when they share one vertex. Counting ordered pairs of -sets gives the exact formula
This includes the diagonal case .
To bound the overlap factor, regard it as the probability that a uniformly chosen -set intersects a fixed in exactly vertices. A union bound over the possible specified -subsets of yields
Here is a falling factorial, and the last bound holds for . Therefore
For , the concave quadratic is minimized at an endpoint. Its endpoint values are and , both at least . Thus every power of in the last sum is at most , and
because the logarithm of its numerator is . The second moment method, or Chebyshev's inequality directly, gives . Finally, every larger clique contains a -clique, so the absence of excludes all larger sizes. The clique number is exactly with high probability: