Set Partition Complexes
2008 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 40, 357-364 p.Article in journal (Refereed) Published
The Hom complexes were introduced by Lovasz 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 Cukic 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.
Place, publisher, year, edition, pages
2008. Vol. 40, 357-364 p.
set partition complex; Hom complex; topological combinatorics; Ramsey theory
IdentifiersURN: urn:nbn:se:kth:diva-10374DOI: 10.1007/s00454-008-9106-6ISI: 000259563600003ScopusID: 2-s2.0-52949094244OAI: oai:DiVA.org:kth-10374DiVA: diva2:216358
QC 201007122009-05-082009-05-082010-12-03Bibliographically approved