Set Partition Complexes |
| |
Authors: | Alexander Engström |
| |
Institution: | (1) Department of Mathematics, Royal Institute of Technology, 100 44 Stockholm, Sweden |
| |
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. |
| |
Keywords: | Set partition complex Hom complex Topological combinatorics Ramsey theory |
本文献已被 SpringerLink 等数据库收录! |
|