Fixed-size clique appearance threshold 2026-10-14
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.
Growing-clique overlap bound 2026-10-14
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.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 12 1 ii Solution Created 2026-10-03 Updated 2026-10-14
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 impliesWe must bound this sum with allowed to grow.
Eventually and . Using , these inequalities giveFor , 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 isFor , the second bound on givesThe 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 thatThus . The second moment method gives . Combining this with the absence of larger cliques provesThe 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 .
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 37 2 b Solution Created 2026-10-03 Updated 2026-10-14
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. ThereforeThere are choices of , then ways to choose the overlap and ways to choose the remaining vertices of . It follows thatA 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 givessince . 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 givesproving 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 probabilityThus 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.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 112 4 Solution Created 2026-10-03 Updated 2026-10-06
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 .
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, soFor their edge sets are disjoint and the covariance vanishes, even when they share one vertex. Counting ordered pairs of -sets gives the exact formulaThis 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 yieldsHere is a falling factorial, and the last bound holds for . ThereforeFor , 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 , andbecause 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: