Kahle's homology vanishing conjecture for random clique complexes

Let G=Gn,pG=G_{n,p} be the Erdős–Rényi random graph, and let X(G)X(G) be its clique complex, whose faces are the vertex sets of cliques of GG. Let Γ\Gamma be either Z\mathbb{Z} or a field, let kk be a positive integer, and let Hk(X(G),Γ)H_k(X(G),\Gamma) denote the kkth homology group. An event holds w.h.p. if its probability tends to 11 as nn\to\infty.

Kahle's homology vanishing conjecture. For each positive integer kk and each ε>0\varepsilon>0, if

p>(1+ε)[(1+k/2)(logn/n)]1/(k+1),p>(1+\varepsilon)\left[(1+k/2)(\log n/n)\right]^{1/(k+1)},

then w.h.p.

Hk(X(G),Γ)=0.H_k(X(G),\Gamma)=0.

The source attributes this conjecture to M. Kahle and notes that it was proved there for Γ=Q\Gamma=\mathbb{Q}. The conjecture concerns the threshold above which the kkth homology of a random clique complex vanishes.

Sources & referencesView supporting material

Primary source

Bobby DeMarco and Jeff Kahn, “Mantel's Theorem for random graphs”, arXiv:1206.1016 (2012).

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.