A simple proof for folds on both sides in complexes of graph homomorphisms
Author:
Dmitry N. Kozlov
Journal:
Proc. Amer. Math. Soc. 134 (2006), 12651270
MSC (2000):
Primary 05C15; Secondary 57M15
Published electronically:
October 6, 2005
MathSciNet review:
2199168
Fulltext 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 is a fold of , then Hom collapses onto Hom, whereas Hom collapses onto Hom. We also give an easy inductive proof of the only nonelementary fact which we use for our arguments: if is a closure operator on , then collapses onto .
 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
(2004i:05044), http://dx.doi.org/10.1090/S1079676203001124
 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
(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.
Sonja
Lj. Čukić and Dmitry
N. Kozlov, Higher connectivity of graph coloring complexes,
Int. Math. Res. Not. 25 (2005), 1543–1562. MR 2152894
(2006c:05055), http://dx.doi.org/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
(99b:57050), http://dx.doi.org/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, SpringerVerlag, Berlin, 1988. MR 932724
(90d:57039)
 11.
D.N. Kozlov, Chromatic numbers, morphism complexes, and StiefelWhitney 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
(49 #2895)
 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
(94h:55032)
 1.
 E. Babson and D.N. Kozlov, Topological obstructions to graph colorings, Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 6168. 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. 18191872. 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), 15431562. 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, 90145. MR 1612391 (99b:57050)
 10.
 M. Goresky and R. MacPherson, Stratified Morse Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 14, SpringerVerlag, Berlin/Heidelberg/New York, 1992. MR 0932724 (90d:57039)
 11.
 D.N. Kozlov, Chromatic numbers, morphism complexes, and StiefelWhitney 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 Ktheory I, Lecture Notes in Mathematics 341, (1973), pp. 77139, SpringerVerlag. MR 0338129 (49:2895)
 13.
 V.A. Vassiliev, Complexes of connected graphs, The Gel'fand Mathematical Seminars, 19901992, pp. 223235, 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
Email:
dkozlov@inf.ethz.ch
DOI:
http://dx.doi.org/10.1090/S0002993905081050
PII:
S 00029939(05)081050
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 PP002102738/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.
