Link collapsibility conjecture for independence complexes of bounded-degree graphs

About 7 years old · traced to

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 n−1n-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 n≥1n\geq 1.

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

C(lk⁡(In(G),A))≤⌊(n−1)Δ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.

References

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.