The asymptotic enumeration conjecture for clique factors in sparse random graphs

Let r3r\geqslant 3 be constant, let pn2/r+o(1)p\leqslant n^{-2/r+o(1)}, and let m=(nr)p(r2)m=\big\lfloor\binom{n}{r}p^{\binom{r}{2}}\big\rfloor. Write Fr(G(n,p))F_r(G(n,p)) for the number of KrK_r-factors in the random graph G(n,p)G(n,p), and let Σ(n,m)\Sigma(n,m) denote the corresponding benchmark quantity. Clique-factor enumeration conjecture. With high probability,

Fr(G(n,p))=eΘ(n3/m2)Σ(n,m)1[Fr(G(n,p))>0].F_r(G(n,p))=e^{-\Theta(n^3/m^2)}\,\Sigma(n,m)\cdot\mathbf{1}\big[F_r(G(n,p))>0\big].

At p=Θ(qr(n))p=\Theta(q_r(n)), the correction term has the form exp(Θ(n/(logn)2))\exp\big(-\Theta(n/(\log n)^2)\big) and reflects variation in the number of intersections between copies of KrK_r. The authors expect the statement to hold up to roughly m=n4/3m=n^{4/3}, where variation in the number of copies of KrK_r has a larger effect.

Sources & referencesView supporting material

Primary source

Robert Morris and Oliver Riordan, “Random cliques in random graphs revisited”, arXiv:2504.00964 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.