Growing clique size can invalidate a first-moment appearance criterion
ID: growing-clique-size-can-invalidate-a-first-moment-appearance-criterion
With these parameters the expected number of -cliques is asymptotic to , yet the probability of any such clique tends to zero. The complement graph has about edges, and with probability tending to one two of them are vertex disjoint. Deleting one vertex cannot remove both edges. Thus divergence of the expected clique count alone does not give an appearance theorem for arbitrary growing clique size.
New to topics? Read the docs here!