Collapsibility bound for independence complexes of bounded-degree graphs

Let GG be a graph, and let In(G)I_n(G) denote its complex of independent sets of size at most nn. For a simplicial complex XX, let C(X)C(X) denote its collapsibility number. Let Δ\Delta be a nonnegative integer and let nn be a positive integer.

Collapsibility conjecture. If GG has maximum degree at most Δ\Delta, then

C(In(G))Δ+12(n1).C(I_n(G))\leq\left\lceil\frac{\Delta+1}{2}\right\rceil(n-1).

This is proposed as an extension of the Aharoni–Briggs–Kim–Kim conjecture. The bound is known for claw-free graphs, but the paper gives counterexamples in general, so the conjecture is refuted.

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.