A simple proof for folds on both sides in complexes of graph homomorphisms
HTML articles powered by AMS MathViewer
- by Dmitry N. Kozlov PDF
- Proc. Amer. Math. Soc. 134 (2006), 1265-1270 Request permission
Abstract:
In this paper we study implications of folds in both parameters of Lovász’ $\mathtt {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 $\operatorname {bd}\mathtt {Hom}(G,H)$ collapses onto $\operatorname {bd}\mathtt {Hom}(G-v,H)$, whereas $\mathtt {Hom}(H,G)$ collapses onto $\mathtt {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
- Eric Babson and Dmitry N. Kozlov, Topological obstructions to graph colorings, Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 61–68. MR 2029466, DOI 10.1090/S1079-6762-03-00112-4
- E. Babson and D.N. Kozlov, Complexes of graph homomorphisms, to appear in Israel J. Math. arXiv:math.CO/0310056
- E. Babson and D.N. Kozlov, Proof of the Lovász Conjecture, to appear in Annals of Mathematics (2). arXiv:math.CO/0402395
- A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
- P. Csorba, private communication, 2004.
- S.Lj. Čukić 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
- Sonja Lj. Čukić and Dmitry N. Kozlov, Higher connectivity of graph coloring complexes, Int. Math. Res. Not. 25 (2005), 1543–1562. MR 2152894, DOI 10.1155/IMRN.2005.1543
- A. Dochtermann, private communication, 2004.
- Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90–145. MR 1612391, DOI 10.1006/aima.1997.1650
- 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, DOI 10.1007/978-3-642-71714-7
- 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.
- Daniel Quillen, Higher algebraic $K$-theory. I, Algebraic $K$-theory, I: Higher $K$-theories (Proc. Conf., Battelle Memorial Inst., Seattle, Wash., 1972) Lecture Notes in Math., Vol. 341, Springer, Berlin, 1973, pp. 85–147. MR 0338129
- 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
Additional Information
- Dmitry N. Kozlov
- Affiliation: Department of Computer Science, Eidgenössische Technische Hochschule, Zürich, Switzerland
- Email: dkozlov@inf.ethz.ch
- 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
- © Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 134 (2006), 1265-1270
- MSC (2000): Primary 05C15; Secondary 57M15
- DOI: https://doi.org/10.1090/S0002-9939-05-08105-0
- MathSciNet review: 2199168