Neighborhood complexes of stable Kneser graphs (Q1878588)

The stable Kneser graph \(\mathrm{SG}_{n,k}\) consists of those \(n\)-element subsets of the cyclically ordered set \(\{1,\dots,2n+k\}\) which contain no 2 consecutive elements, with two such \(n\)-sets joined if and only if they are disjoint. It is shown that the neighborhood complex of \(\mathrm{SG}_{n,k}\) is homotopy equivalent to the sphere \({\mathbf S}^k\) for \(n\geq 1\), \(k\geq 0\). The neighborhood complex of \(\mathrm{SG}_{2,k}\) contains, as a deformation retract, the simplicial complex encoding triangulations of a \((k+4)\)-gon.