zbMATH — the first resource for mathematics

Complexes of graph homomorphisms. (English) Zbl 1205.52009
For any two graphs \(G\) and \(H\) there is a polyhedral complex \({\operatorname{Hom}}(G,H)\), the Hom-complex of \(G\) and \(H\), whose vertices are the graph homomorphisms from \(G\) to \(H\). Especially interesting are the complexes \({\operatorname{Hom}}(G,K_n)\) where \(K_n\) is the complete graph on \(n\) nodes. This complex is non-empty if and only if \(G\) admits a proper coloring of its nodes with \(n\) colors.
In the paper under review the authors prove a number of combinatorial and topological results about Hom-complexes. In particular, they show that \({\operatorname{Hom}}(K_2,G)\) is homotopy equivalent to the neighborhood complex of \(G\). The degree of connectedness of the latter is known to form an obstruction to the colorability of \(G\) from L. Lovász’ solution of the Kneser conjecture [J. Comb. Theory, Ser. A 25, 319–324 (1978; Zbl 0418.05028)].
Moreover, it is proved that \({\operatorname{Hom}}(K_m,K_n)\) is homotopy equivalent to a wedge of \((n-m)\)-dimensional spheres, and a recurrence relation is given for their number. Other results involve the computation of homotopy types of Hom-complexes from finite forests to complete graphs. The techniques developed in this paper were applied in the authors’ proof [Ann. Math. (2) 165, No. 3, 965–1007 (2007; Zbl 1132.05019)] of a conjecture of Lovász.

52B70 Polyhedral manifolds
05C15 Coloring of graphs and hypergraphs
Full Text: DOI arXiv
[1] N. Alon, P. Frankl and L. Lovász,The chromatic number of Kneser hypergraphs, Transactions of the American Mathematical Society298 (1986), 359–370. · Zbl 0605.05033 · doi:10.1090/S0002-9947-1986-0857448-8
[2] E. Babson,A combinatorial flag space, Ph.D. Thesis, MIT, 1993.
[3] E. Babson, A. Björner, S. Linusson, J. Shareshian and V. Welker,Complexes of not i-connected graphs, Topology38 (1999), 271–299. · Zbl 0936.57002 · doi:10.1016/S0040-9383(98)00009-3
[4] E. Babson and D. N. Kozlov,Topological obstructions to graph colorings, Electronic Research Announcements of the American Mathematical Society9 (2003), 61–68. · Zbl 1063.05041 · doi:10.1090/S1079-6762-03-00112-4
[5] E. Babson and D. N. Kozlov,Proof of the Lovász Conjecture, preprint, 40 pages, 2004.arXiv:math.C0/0402395
[6] 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. · Zbl 0453.55003 · doi:10.1112/jlms/s2-23.1.158
[7] A. Björner,Topological Methods, inHandbook of Combinatorics (R. Graham, M. Grötschel and L. Lovász, eds.), Elsevier, Amsterdam, 1995, pp. 1819–1872.
[8] G. Bredon,Topology and Geometry, Corrected third printing of the 1993 original, Graduate Texts in Mathematics,139, Springer-Verlag, New York, 1997.
[9] 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. · Zbl 0988.53001
[10] P. Csorba, personal communication, 2003.
[11] P. Csorba and F. Lutz, personal communication, 2004.
[12] S. Lj. Čukić and D. N. Kozlov,Complexes of graph homomorphisms between cycles, 15 pages, preprint 2004.arXiv:math.C0/0408015
[13] S. Lj. Čukić and D. N. Kozlov,Higher connectivity of graph coloring complexes, International Mathematics Research Notices25 (2005), 1543–1562. · Zbl 1077.05038
[14] R. Forman,Morse theory for cell complexes, Advances in Mathematics134 (1998), 90–145. · Zbl 0896.57023 · doi:10.1006/aima.1997.1650
[15] S. Hoory and N. Linial,A counterexample to a conjecture of Lovász on the \(\chi\)-coloring complex, 3 pages, preprint 2004.arXiv:math.C0/0405339
[16] M. Kneser,Aufgabe 360, Jahresbericht der Deutscher Mathematiker Vereinigung58 (1955), 27.
[17] D. N. Kozlov,Collapsibility of \(\Delta\)(\(\Pi\) n )/S n and some related CW complexes, Proceedings of the American Mathematical Society128 (2000), 2253–2259. · Zbl 0939.05086 · doi:10.1090/S0002-9939-99-05301-0
[18] D. N. Kozlov,Rational homology of spaces of complex monic polynomials with multiple roots, Mathematika49 (2002), 77–91. · Zbl 1065.58027 · doi:10.1112/S0025579300016089
[19] 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 · Zbl 1081.05035
[20] D. N. Kozlov,Simple homotopy type of some combinatorially defined complexes, 12 pages, preprint 2005.arXiv:math.AT/0503613
[21] 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. · Zbl 1139.05022
[22] L. Lovász,Kneser’s conjecture, chromatic number, and homotopy, Journal of Combinatorial Theory. Series A25 (1978), 319–324. · Zbl 0418.05028 · doi:10.1016/0097-3165(78)90022-5
[23] L. Lovász, personal communication, 2001.
[24] J. Matoušek,Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003, xii+196 pp.
[25] J. Matoušek and G. M. Ziegler,Topological lower bounds for the chromatic number: A hierarchy, Jahresbericht der Deutscher Mathematiker Vereinigung106 (2004), 71–90. · Zbl 1063.05047
[26] D. Quillen,Higher algebraic K-theory, I, Lecture Notes in Mathematics341, Springer-Verlag, Berlin, 1973, pp. 77–139.
[27] B. Sturmfels and G. M. Ziegler,Extension spaces of oriented matroids, Discrete and Computational Geometry10 (1993), 23–45. · Zbl 0783.52009 · doi:10.1007/BF02573961
[28] T. tom Dieck,Transformation Groups, de Gruyter Studies in Mathematics, 8, Walter de Gruyter & Co., Berlin, 1987, x+312 pp. · Zbl 0611.57002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.