Abstract
The Hom complexes were introduced by Lovász to study topological obstructions to graph colorings. The vertices of Hom(G,K n ) are the n-colorings of the graph G, and a graph coloring is a partition of the vertex set into independent sets. Replacing the independence condition with any hereditary condition defines a set partition complex. We show how coloring questions arising from, for example, Ramsey theory can be formulated with set partition complexes.
It was conjectured by Babson and Kozlov, and proved by Čukić and Kozlov, that Hom(G,K n ) is (n−d−2)-connected, where d is the maximal degree of a vertex of G. We generalize this to set partition complexes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Babson, E., Kozlov, D.N.: Complexes of graph homomorphisms. Israel J. Math. 152, 282–312 (2006)
Babson, E., Kozlov, D.N.: Proof of the Lovász conjecture. Ann. Math. (2) 165(3), 965–1007 (2007)
Björner, A.: Topological Methods. In: Graham, R., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, pp. 1819–1872. North-Holland, Amsterdam (1995)
Čukić, S.Lj., Kozlov, D.N.: Higher connectivity of graph coloring complexes. Int. Math. Res. Not. 2005(25), 1543–1562 (2005)
Čukić, S.Lj., Kozlov, D.N.: The homotopy type of complexes of graph homomorphisms between cycles. Discrete Comput. Geom. 36(2), 313–329 (2006)
Dochtermann, A.: Hom complexes and homotopy theory in the category of graphs. Eur. J. Comb. (2008). doi:10.1016/j.ejc.2008.04.009
Dochtermann, A.: Homotopy groups of Hom complexes of graphs. J. Comb. Theory Ser. A (2008). doi:10.1016/j.jcta.2008.06.001
Dochtermann, A.: The universality of Hom complexes. Combinatorica (to appear)
Engström, A.: A short proof of a conjecture on the connectivity of graph coloring complexes. Proc. Am. Math. Soc. 134(12), 3703–3705 (2006)
Engström, A.: Cohomological Ramsey theory (in preparation)
Forman, R.: Morse theory for cell complexes. Adv. Math. 134(1), 90–145 (1998)
Graham, R.L., Rothschild, B.L., Spencer, J.H.: Ramsey Theory. Wiley-Interscience Series in Discrete Mathematics. Wiley, New York (1980)
Jonsson, J.: Simplicial Complexes of Graphs. Lecture Notes in Mathematics, vol. 1928, Springer, Berlin (2008)
Kozlov, D.N.: Chromatic numbers, morphism complexes, and Stiefel–Whitney characteristic classes. In: Miller, E., Reiner, V., Sturmfels, B. (eds.) Geometric Combinatorics. Lectures from the Graduate Summer School held in Park City, UT, 2004. IAS/Park City Mathematics Series, vol. 13. American Mathematical Society/Institute for Advanced Study (IAS), Providence/Princeton (2007)
Lundell, A., Weingram, S.: The Topology of CW Complexes. Van Nostrand-Reinhold, New York (1969)
Schultz, C.: A short proof of w n1 (Hom(C 2r+1,K n+2))=0 for all n and a graph colouring theorem by Babson and Kozlov. Israel J. Math. (to appear)
Schultz, C.: Graph colourings, spaces of edges and spaces of circuits, Adv. Math. (to appear)
Tao, T., Vu, V.: Additive combinatorics. Cambridge Studies in Advanced Mathematics, vol. 105. Cambridge University Press, Cambridge (2006)
Živaljević, R.T.: Combinatorial groupoids, cubical complexes, and the Lovász conjecture. Discrete Comput. Geom. (to appear)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Engström, A. Set Partition Complexes. Discrete Comput Geom 40, 357–364 (2008). https://doi.org/10.1007/s00454-008-9106-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9106-6