Deformation retracts of neighborhood complexes of stable Kneser graphs
HTML articles powered by AMS MathViewer
- by Benjamin Braun and Matthew Zeckner PDF
- Proc. Amer. Math. Soc. 142 (2014), 413-427 Request permission
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
- Eric Babson and Dmitry N. Kozlov, Complexes of graph homomorphisms, Israel J. Math. 152 (2006), 285–312. MR 2214465, DOI 10.1007/BF02771988
- Eric Babson and Dmitry N. Kozlov, Proof of the Lovász conjecture, Ann. of Math. (2) 165 (2007), no. 3, 965–1007. MR 2335799, DOI 10.4007/annals.2007.165.965
- Anders Björner and Mark De Longueville, Neighborhood complexes of stable Kneser graphs, Combinatorica 23 (2003), no. 1, 23–34. Paul Erdős and his mathematics (Budapest, 1999). MR 1996625, DOI 10.1007/s00493-003-0012-5
- 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, DOI 10.1016/j.ejc.2010.06.005
- Benjamin Braun, Symmetries of the stable Kneser graphs, Adv. in Appl. Math. 45 (2010), no. 1, 12–14. MR 2628781, DOI 10.1016/j.aam.2009.11.009
- Benjamin Braun, Independence complexes of stable Kneser graphs, Electron. J. Combin. 18 (2011), no. 1, Paper 118, 17. MR 2811087
- Anton Dochtermann and Alexander Engström, Cellular resolutions of cointerval ideals, Math. Z. 270 (2012), no. 1-2, 145–163. MR 2875826, DOI 10.1007/s00209-010-0789-z
- Anton Dochtermann and Carsten Schultz, Topology of Hom complexes and test graphs for bounding chromatic number, Israel J. Math. 187 (2012), 371–417. MR 2891708, DOI 10.1007/s11856-011-0085-6
- Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90–145. MR 1612391, DOI 10.1006/aima.1997.1650
- Jakob Jonsson, Simplicial complexes of graphs, Lecture Notes in Mathematics, vol. 1928, Springer-Verlag, Berlin, 2008. MR 2368284, DOI 10.1007/978-3-540-75859-4
- Dmitry Kozlov, Combinatorial algebraic topology, Algorithms and Computation in Mathematics, vol. 21, Springer, Berlin, 2008. MR 2361455, DOI 10.1007/978-3-540-71962-5
- Gui Zhen Liu, Proof of a conjecture on matroid base graphs, Sci. China Ser. A 33 (1990), no. 11, 1329–1337. MR 1084957
- L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324. MR 514625, DOI 10.1016/0097-3165(78)90022-5
- A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. (3) 26 (1978), no. 3, 454–461. MR 512648
- Carsten Schultz, Graph colorings, spaces of edges and spaces of circuits, Adv. Math. 221 (2009), no. 6, 1733–1756. MR 2522827, DOI 10.1016/j.aim.2009.03.006
- Carsten Schultz, The equivariant topology of stable Kneser graphs, J. Combin. Theory Ser. A 118 (2011), no. 8, 2291–2318. MR 2834178, DOI 10.1016/j.jcta.2011.04.009
- Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1
Additional Information
- Benjamin Braun
- Affiliation: Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506
- MR Author ID: 797231
- Email: benjamin.braun@uky.edu
- Matthew Zeckner
- Affiliation: Adrian College, 110 S. Madison Street, Adrian, Michigan 49221-2575
- Email: mzeckner@adrian.edu
- 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
- © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 142 (2014), 413-427
- MSC (2010): Primary 05E45; Secondary 57M15, 05E18, 05C15
- DOI: https://doi.org/10.1090/S0002-9939-2013-11803-4
- MathSciNet review: 3133984