Abstract
Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes.
We prove that Hom(K m, Kn) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ k1 (Hom(K m, G))≠0, thenχ(G)≥k+m; here ℤ2-action is induced by the swapping of two vertices inK m, and ϖ1 is the first Stiefel-Whitney class corresponding to this action.
Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon, P. Frankl and L. Lovász,The chromatic number of Kneser hypergraphs, Transactions of the American Mathematical Society298 (1986), 359–370.
E. Babson,A combinatorial flag space, Ph.D. Thesis, MIT, 1993.
E. Babson, A. Björner, S. Linusson, J. Shareshian and V. Welker,Complexes of not i-connected graphs, Topology38 (1999), 271–299.
E. Babson and D. N. Kozlov,Topological obstructions to graph colorings, Electronic Research Announcements of the American Mathematical Society9 (2003), 61–68.
E. Babson and D. N. Kozlov,Proof of the Lovász Conjecture, preprint, 40 pages, 2004.arXiv:math.C0/0402395
I. Bárány, S. B. Shlosman and A. Szucs,On a topological generalization of a theorem of Tverberg, Journal of the London Mathematical Society (2)23 (1981), 158–164.
A. Björner,Topological Methods, inHandbook of Combinatorics (R. Graham, M. Grötschel and L. Lovász, eds.), Elsevier, Amsterdam, 1995, pp. 1819–1872.
G. Bredon,Topology and Geometry, Corrected third printing of the 1993 original, Graduate Texts in Mathematics,139, Springer-Verlag, New York, 1997.
M. R. Bridson and A. Haefliger,Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]319, Springer-Verlag, Berlin, 1999.
P. Csorba, personal communication, 2003.
P. Csorba and F. Lutz, personal communication, 2004.
S. Lj. Čukić and D. N. Kozlov,Complexes of graph homomorphisms between cycles, 15 pages, preprint 2004.arXiv:math.C0/0408015
S. Lj. Čukić and D. N. Kozlov,Higher connectivity of graph coloring complexes, International Mathematics Research Notices25 (2005), 1543–1562.
R. Forman,Morse theory for cell complexes, Advances in Mathematics134 (1998), 90–145.
S. Hoory and N. Linial,A counterexample to a conjecture of Lovász on the χ-coloring complex, 3 pages, preprint 2004.arXiv:math.C0/0405339
M. Kneser,Aufgabe 360, Jahresbericht der Deutscher Mathematiker Vereinigung58 (1955), 27.
D. N. Kozlov,Collapsibility of Δ(Π n )/S n and some related CW complexes, Proceedings of the American Mathematical Society128 (2000), 2253–2259.
D. N. Kozlov,Rational homology of spaces of complex monic polynomials with multiple roots, Mathematika49 (2002), 77–91.
D. N. Kozlov,A simple proof for folds on both sides in complexes of graph homomorphisms, Proceedings of the American Mathematical Society, to appear.arXiv:math.C0/0408262
D. N. Kozlov,Simple homotopy type of some combinatorially defined complexes, 12 pages, preprint 2005.arXiv:math.AT/0503613
D. N. Kozlov,Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes, inGeometric Combinatorics, IAS/Park City Mathematics Series14, American Mathematical Society, Providence, RI; Institute for Advanced Study (IAS), Princeton, NJ, 2005.
L. Lovász,Kneser’s conjecture, chromatic number, and homotopy, Journal of Combinatorial Theory. Series A25 (1978), 319–324.
L. Lovász, personal communication, 2001.
J. Matoušek,Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003, xii+196 pp.
J. Matoušek and G. M. Ziegler,Topological lower bounds for the chromatic number: A hierarchy, Jahresbericht der Deutscher Mathematiker Vereinigung106 (2004), 71–90.
D. Quillen,Higher algebraic K-theory, I, Lecture Notes in Mathematics341, Springer-Verlag, Berlin, 1973, pp. 77–139.
B. Sturmfels and G. M. Ziegler,Extension spaces of oriented matroids, Discrete and Computational Geometry10 (1993), 23–45.
T. tom Dieck,Transformation Groups, de Gruyter Studies in Mathematics, 8, Walter de Gruyter & Co., Berlin, 1987, x+312 pp.
Author information
Authors and Affiliations
Corresponding author
Additional information
The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.
Rights and permissions
About this article
Cite this article
Babson, E., Kozlov, D.N. Complexes of graph homomorphisms. Isr. J. Math. 152, 285–312 (2006). https://doi.org/10.1007/BF02771988
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02771988