Fixed-size clique appearance threshold

ID: fixed-size-clique-appearance-threshold

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.

New to topics? Read the docs here!