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)



A simple proof for folds on both sides in complexes of graph homomorphisms

Author: Dmitry N. Kozlov
Journal: Proc. Amer. Math. Soc. 134 (2006), 1265-1270
MSC (2000): Primary 05C15; Secondary 57M15
Published electronically: October 6, 2005
MathSciNet review: 2199168
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we study implications of folds in both parameters of Lovász' Hom$ (-,-)$ complexes. There is an important connection between the topological properties of these complexes and lower bounds for chromatic numbers. We give a very short and conceptual proof of the fact that if $ G-v$ is a fold of $ G$, then $ {bd}$Hom$ (G,H)$ collapses onto $ {bd}$Hom$ (G-v,H)$, whereas Hom$ (H,G)$ collapses onto Hom$ (H,G-v)$.

We also give an easy inductive proof of the only nonelementary fact which we use for our arguments: if $ \varphi$ is a closure operator on $ P$, then $ \Delta(P)$ collapses onto $ \Delta(\varphi(P))$.

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

  • 1. Eric Babson and Dmitry N. Kozlov, Topological obstructions to graph colorings, Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 61–68 (electronic). MR 2029466, 10.1090/S1079-6762-03-00112-4
  • 2. E. Babson and D.N. Kozlov, Complexes of graph homomorphisms, to appear in Israel J. Math. arXiv:math.CO/0310056
  • 3. E. Babson and D.N. Kozlov, Proof of the Lovász Conjecture, to appear in Annals of Mathematics (2). arXiv:math.CO/0402395
  • 4. A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 1819–1872. MR 1373690
  • 5. P. Csorba, private communication, 2004.
  • 6. S.Lj. Cukic and D.N. Kozlov, The homotopy type of the complexes of graph homomorphisms between cycles, to appear in Discrete Comput. Geom. arXiv:math.CO/0408015
  • 7. Sonja Lj. Čukić and Dmitry N. Kozlov, Higher connectivity of graph coloring complexes, Int. Math. Res. Not. 25 (2005), 1543–1562. MR 2152894, 10.1155/IMRN.2005.1543
  • 8. A. Dochtermann, private communication, 2004.
  • 9. Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90–145. MR 1612391, 10.1006/aima.1997.1650
  • 10. Mark Goresky and Robert MacPherson, Stratified Morse theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 14, Springer-Verlag, Berlin, 1988. MR 932724
  • 11. D.N. Kozlov, Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes, to appear in ``Geometric Combinatorics", IAS/Park City Mathematical Series 14, AMS, Providence, RI; Institute for Advanced Study (IAS), Princeton, NJ.
  • 12. Daniel Quillen, Higher algebraic 𝐾-theory. I, Algebraic 𝐾-theory, I: Higher 𝐾-theories (Proc. Conf., Battelle Memorial Inst., Seattle, Wash., 1972) Springer, Berlin, 1973, pp. 85–147. Lecture Notes in Math., Vol. 341. MR 0338129
  • 13. V. A. Vassiliev, Complexes of connected graphs, The Gel′fand Mathematical Seminars, 1990–1992, Birkhäuser Boston, Boston, MA, 1993, pp. 223–235. MR 1247293

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 05C15, 57M15

Additional Information

Dmitry N. Kozlov
Affiliation: Department of Computer Science, Eidgenössische Technische Hochschule, Zürich, Switzerland

Keywords: Graphs, graph homomorphisms, \text{\tt{Hom}} complex, closure operator, collapse, fold, order complex, discrete Morse theory, graph coloring
Received by editor(s): September 1, 2004
Received by editor(s) in revised form: December 2, 2004
Published electronically: October 6, 2005
Additional Notes: This research was supported by Swiss National Science Foundation Grant PP002-102738/1
Communicated by: Paul Goerss
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.