The asymptotic formula for cliques in a random uniform hypergraph

From papers

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)(1p(kr1))nk.\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((lognlogp)1r1((11r!)logn1r1loglogn+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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.