Topology of Hom complexes and test graphs for bounding chromatic number
arXiv:0907.5079
Abstract
We introduce new methods for understanding the topology of $\Hom$ complexes (spaces of homomorphisms between two graphs), mostly in the context of group actions on graphs and posets. We view $\Hom(T,-)$ and $\Hom(-,G)$ as functors from graphs to posets, and introduce a functor from posets to graphs obtained by taking atoms as vertices. Our main structural results establish useful interpretations of the equivariant homotopy type of $\Hom$ complexes in terms of spaces of equivariant poset maps and -twisted products of spaces. When is the face poset of a simplicial complex , this provides a useful way to control the topology of $\Hom$ complexes. Our foremost application of these results is the construction of new families of `test graphs' with arbitrarily large chromatic number - graphs with the property that the connectivity of $\Hom(T,G)$ provides the best possible lower bound on the chromatic number of . In particular we focus on two infinite families, which we view as higher dimensional analogues of odd cycles. The family of `spherical graphs' have connections to the notion of homomorphism duality, whereas the family of `twisted toroidal graphs' lead us to establish a weakened version of a conjecture (due to Lovász) relating topological lower bounds on chromatic number to maximum degree. Other structural results allow us to show that any finite simplicial complex with a free action by the symmetric group can be approximated up to -homotopy equivalence as $\Hom(K_n,G)$ for some graph ; this is a generalization of a result of Csorba. We conclude the paper with some discussion regarding the underlying categorical notions involved in our study.
arXiv comment42 pages, 3 figures; incorporated referee's comments and corrections, to appear in Israel J. Math.