← All problems

Connectivity conjecture for random graph neighborhood complexes

24 years old · documented by

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 k≥s≥1k\geq s\geq 1, write o(ns)o(n^s) with respect to n→∞n\to\infty.

Connectivity conjecture. If

(nk+2)(1−pk+2)n−k−2=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 (k−s+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.

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.

Source: Xiongfeng Zhan, Xueyi Huang and Jin-Xin Zhou, “Eigenvalue bounds for combinatorial Laplacians and an application to random complexes”, arXiv:2510.25083 (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.