= Growing clique size can invalidate a first-moment appearance criterion
{title2=$k=n-1,\quad p=1-(\log n)/n^2$}
With these parameters the expected number of $(n-1)$-cliques is asymptotic to $\sqrt n$, yet the probability of any such <clique> tends to zero. The complement graph has about $\tfrac12\log n$ 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.
Back to article page
