The asymptotic formula for cliques in a random uniform hypergraph

About 4 years old · traced to

Let G(r)(n,p)G^{(r)}(n,p) be the random rr-uniform hypergraph on nn vertices in which each possible hyperedge occurs independently with probability pp, and let Xn,p(r)X_{n,p}^{(r)} count its maximal complete subhypergraphs. Then

E[Xn,p(r)]=∑k=1n(nk)p(kr)(1−p(kr−1))n−k.\mathbb E[X_{n,p}^{(r)}]=\sum_{k=1}^n \binom nk p^{\binom kr}(1-p^{\binom k{r-1}})^{n-k}.

Asymptotic clique-count conjecture. The expected number of cliques satisfies

E[Xn,p(r)]=exp⁡((log⁡n−log⁡p)1r−1((1−1r!)log⁡n−1r−1log⁡log⁡n+O(1))).\mathbb E[X_{n,p}^{(r)}]=\exp\left( \left(\frac{\log n}{-\log p}\right)^{\frac1{r-1}} \left( (1-\tfrac1{r!})\log n-\tfrac1{r-1}\log\log n +O(1) \right) \right).

This extends the problem of counting cliques in G(n,p)G(n,p) to uniform hypergraphs. The supplied text does not state whether this asymptotic formula has been proved or remains open.

References

Primary source

Taro Sakurai and Norihide Tokushige, “Counting cliques in a random graph”, arXiv:2208.07492 (2022).

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.