Deformation retracts of neighborhood complexes of stable Kneser graphs

Abstract:

In 2003, A. Björner and M. de Longueville proved that the neighborhood complex of the stable Kneser graph $SG_{n,k}$ is homotopy equivalent to a $k$-sphere. Further, for $n=2$ they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron. They went on to ask whether or not, for all $n$ and $k$, the neighborhood complex of $SG_{n,k}$ contains as a deformation retract the boundary complex of a simplicial polytope.

Our purpose is to give a positive answer to this question in the case $k=2$. We also find in this case that, after partially subdividing the neighborhood complex, the resulting complex deformation retracts onto a subcomplex arising as a polyhedral boundary sphere that is invariant under the action induced by the automorphism group of $SG_{n,2}$.