Link collapsibility conjecture for independence complexes of bounded-degree graphs

Let G=(V,E)G=(V,E) be a graph with maximum degree at most Δ\Delta, and let In(G)I_n(G) be its independence complex. For an independent set AA of size n1n-1, let lk(In(G),A)\operatorname{lk}(I_n(G),A) denote the link of AA in In(G)I_n(G). Let C(X)C(X) denote the collapsibility number of a simplicial complex XX, and let n1n\geq 1.

Link collapsibility conjecture. If AA is an independent set of size n1n-1 in GG, then

C(lk(In(G),A))(n1)Δ2.C(\operatorname{lk}(I_n(G),A))\leq\left\lfloor\frac{(n-1)\Delta}{2}\right\rfloor.

This is presented as a weaker result that may hold for general bounded-degree graphs, after the stronger global collapsibility bound was disproved. Its status is open in the supplied text.

Sources & referencesView supporting material

Primary source

Minki Kim and Alan Lew, “Complexes of graphs with bounded independence number”, arXiv:1912.12605 (2019).

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.