Random cliques in random graphs revisited

Abstract

We study the distribution of the set of copies of some given graph $H$ in the random graph $G(n,p)$, focusing on the case when $H=K_r$. Our main results capture the 'leading term' in the difference between this distribution and the 'independent hypergraph model', where (in the case $H=K_r$) each copy is present independently with probability $\ddot{I}€=p^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$. As a concrete application, we derive a new upper bound on the number of $K_r$-factors in $G(n,p)$ above the threshold for such factors to appear. We will prove our main results in a much more general setting, so that they also apply to random hypergraphs, and also (for example) to the case when $p$ is constant and $r=r(n)\sim 2{\log }_{1/p}(n)$.

51 pages