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

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. E. Babson and D.N. Kozlov, Topological obstructions to graph colorings, Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 61-68. MR 2029466 (2004i:05044)
  • 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, in ``Handbook of Combinatorics'' (eds. R. Graham, M. Grötschel and L. Lovász), Elsevier, Amsterdam, 1995, pp. 1819-1872. MR 1373690 (96m:52012)
  • 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. S.Lj. Cukic and D.N. Kozlov, Higher connectivity of graph coloring complexes, Int. Math. Res. Not. no. 25 (2005), 1543-1562. arXiv:math.CO/0410335 MR 2152894
  • 8. A. Dochtermann, private communication, 2004.
  • 9. R. Forman, Morse theory for cell complexes, Adv. Math. 134, (1998), no. 1, 90-145. MR 1612391 (99b:57050)
  • 10. M. Goresky and R. MacPherson, Stratified Morse Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 14, Springer-Verlag, Berlin/Heidelberg/New York, 1992. MR 0932724 (90d:57039)
  • 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. D. Quillen, Higher algebraic K-theory I, Lecture Notes in Mathematics 341, (1973), pp. 77-139, Springer-Verlag. MR 0338129 (49:2895)
  • 13. V.A. Vassiliev, Complexes of connected graphs, The Gel'fand Mathematical Seminars, 1990-1992, pp. 223-235, Birkhäuser Boston, Boston, MA, 1993. MR 1247293 (94h:55032)

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.

American Mathematical Society