{
  "id": "0907.5079",
  "version": "v2",
  "published": "2009-07-29T09:37:31.000Z",
  "updated": "2010-03-23T19:55:09.000Z",
  "title": "Topology of Hom complexes and test graphs for bounding chromatic number",
  "authors": [
    "Anton Dochtermann",
    "Carsten Schultz"
  ],
  "comment": "42 pages, 3 figures; incorporated referee's comments and corrections, to appear in Israel J. Math.",
  "categories": [
    "math.CO",
    "math.AT"
  ],
  "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 $(-)^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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-03-23T19:55:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "57M15",
      "55P99",
      "18D20"
    ],
    "keywords": [
      "bounding chromatic number",
      "test graphs",
      "hom complexes",
      "results establish useful interpretations",
      "structural results establish useful"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 42,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0907.5079D"
    }
  }
}