Deformation retracts of neighborhood complexes of stable kneser graphs

Benjamin Braun, Matthew Zeckner

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In 2003, A. Björner and M. de Longueville proved that the neighborhood complex of the stable Kneser graph SGn,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 SGn,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 SGn,2.

Original languageEnglish
Pages (from-to)413-427
Number of pages15
JournalProceedings of the American Mathematical Society
Issue number2
StatePublished - 2014


  • Discrete morse theory
  • Neighborhood complex
  • Polytope
  • Stable kneser graph

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Deformation retracts of neighborhood complexes of stable kneser graphs'. Together they form a unique fingerprint.

Cite this