Topology of Hom complexes and test graphs for bounding chromatic number

Details Topology of Hom complexes and test graphs for bounding chromatic number Topology of Hom complexes and test graphs for bounding chromatic number

2009-07-29

arxiv.org/abs/0907.5079v2

Mathematics

Combinatorics

42 pages, 3 figures; incorporated referee's comments and corrections, to appear in Israel J. Math.

Scientific paper

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 $(-)^1$ 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 $\Gamma$-twisted products of spaces. When $P = F(X)$ is the face poset of a simplicial complex $X$, 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 $T$ with the property that the connectivity of $\Hom(T,G)$ provides the best possible lower bound on the chromatic number of $G$. 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\'{a}sz) relating topological lower bounds on chromatic number to maximum degree. Other structural results allow us to show that any finite simplicial complex $X$ with a free action by the symmetric group $S_n$ can be approximated up to $S_n$-homotopy equivalence as $\Hom(K_n,G)$ for some graph $G$; 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.

Affiliated with

Also associated with

No associations

Rating

Topology of Hom complexes and test graphs for bounding chromatic number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Topology of Hom complexes and test graphs for bounding chromatic number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topology of Hom complexes and test graphs for bounding chromatic number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521436