Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Deformation retracts of neighborhood complexes of stable Kneser graphs

Authors: Benjamin Braun and Matthew Zeckner
Journal: Proc. Amer. Math. Soc. 142 (2014), 413-427
MSC (2010): Primary 05E45; Secondary 57M15, 05E18, 05C15
Published electronically: November 5, 2013
MathSciNet review: 3133984
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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}$.

References [Enhancements On Off] (What's this?)

  • [1] Eric Babson and Dmitry N. Kozlov, Complexes of graph homomorphisms, Israel J. Math. 152 (2006), 285-312. MR 2214465 (2007b:52024),
  • [2] Eric Babson and Dmitry N. Kozlov, Proof of the Lovász conjecture, Ann. of Math. (2) 165 (2007), no. 3, 965-1007. MR 2335799 (2008i:05059),
  • [3] Anders Björner and Mark De Longueville, Neighborhood complexes of stable Kneser graphs, Paul Erdős and his mathematics (Budapest, 1999), Combinatorica 23 (2003), no. 1, 23-34. MR 1996625 (2004e:05072),
  • [4] Anders Björner and Kathrin Vorwerk, Connectivity of chamber graphs of buildings and related complexes, European J. Combin. 31 (2010), no. 8, 2149-2160. MR 2718289 (2012d:05205),
  • [5] Benjamin Braun, Symmetries of the stable Kneser graphs, Adv. in Appl. Math. 45 (2010), no. 1, 12-14. MR 2628781 (2011d:05165),
  • [6] Benjamin Braun, Independence complexes of stable Kneser graphs, Electron. J. Combin. 18 (2011), no. 1, Paper 118, 17. MR 2811087
  • [7] Anton Dochtermann and Alexander Engström, Cellular resolutions of cointerval ideals, Math. Z. 270 (2012), no. 1-2, 145-163. MR 2875826 (2012m:13039),
  • [8] Anton Dochtermann and Carsten Schultz.
    Topology of Hom complexes and test graphs for bounding chromatic number.
    Israel Journal of Math. 187 (2012), 371-417.MR 2891708
  • [9] Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90-145. MR 1612391 (99b:57050),
  • [10] Jakob Jonsson, Simplicial complexes of graphs, Lecture Notes in Mathematics, vol. 1928, Springer-Verlag, Berlin, 2008. MR 2368284 (2010c:05036)
  • [11] Dmitry Kozlov, Combinatorial algebraic topology, Algorithms and Computation in Mathematics, vol. 21, Springer, Berlin, 2008. MR 2361455 (2008j:55001)
  • [12] Gui Zhen Liu, Proof of a conjecture on matroid base graphs, Sci. China Ser. A 33 (1990), no. 11, 1329-1337. MR 1084957 (92b:05057)
  • [13] L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319-324. MR 514625 (81g:05059),
  • [14] A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. (3) 26 (1978), no. 3, 454-461. MR 512648 (80g:05037)
  • [15] Carsten Schultz, Graph colorings, spaces of edges and spaces of circuits, Adv. Math. 221 (2009), no. 6, 1733-1756. MR 2522827 (2010m:57002),
  • [16] Carsten Schultz, The equivariant topology of stable Kneser graphs, J. Combin. Theory Ser. A 118 (2011), no. 8, 2291-2318. MR 2834178 (2012i:05068),
  • [17] Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028 (96a:52011)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05E45, 57M15, 05E18, 05C15

Retrieve articles in all journals with MSC (2010): 05E45, 57M15, 05E18, 05C15

Additional Information

Benjamin Braun
Affiliation: Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506

Matthew Zeckner
Affiliation: Adrian College, 110 S. Madison Street, Adrian, Michigan 49221-2575

Keywords: Stable Kneser graph, neighborhood complex, discrete Morse theory, polytope
Received by editor(s): April 4, 2011
Received by editor(s) in revised form: March 27, 2012
Published electronically: November 5, 2013
Additional Notes: The first author was partially supported through NSF award DMS-0758321.
The second author was partially supported by a graduate fellowship through NSF award DMS-0758321.
The authors thank the anonymous referee for the reference to Liu’s characterization of $3$-connected graphs.
Communicated by: Jim Haglund
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society