Set partition complexes
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.
set partition complex hom complex ramsey theory topological combinatorics