Connectivity conjecture for random graph neighborhood complexes

Let G(n,p)G(n,p) be the binomial random graph, and let N[G(n,p)]\mathcal{N}[G(n,p)] denote its neighborhood complex. For integers ks1k\geq s\geq 1, write o(ns)o(n^s) with respect to nn\to\infty.

Connectivity conjecture. If

(nk+2)(1pk+2)nk2=o(ns),\binom{n}{k+2}(1-p^{k+2})^{n-k-2}=o(n^s),

then N[G(n,p)]\mathcal{N}[G(n,p)] is asymptotically almost surely (ks+1)(k-s+1)-connected.

This would strengthen the cited connectivity result for the case s=1s=1; the conjecture is presented as a direction for further research, and no resolution is given in the source.

Sources & referencesView supporting material

Primary source

Xiongfeng Zhan, Xueyi Huang and Jin-Xin Zhou, “Eigenvalue bounds for combinatorial Laplacians and an application to random complexes”, arXiv:2510.25083 (2025).

Additional references

14 papers in this index state this conjecture (2001–2025). The statement above is taken from the most recent of them; the others are arXiv:2212.13096, arXiv:2210.09635, arXiv:2110.12264, arXiv:2004.14526, arXiv:1904.08989, arXiv:1601.08199, arXiv:1510.03598, arXiv:1211.4250, arXiv:1108.1571, arXiv:0910.4774, arXiv:math/0701578, arXiv:math/0110233, and 1 more.

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.