{
  "id": "1101.0840",
  "version": "v2",
  "published": "2011-01-04T22:28:36.000Z",
  "updated": "2012-06-14T03:28:33.000Z",
  "title": "H-coloring tori",
  "authors": [
    "John Engbers",
    "David Galvin"
  ],
  "comment": "29 pages, some corrections and minor revisions from earlier version, this version to appear in Journal of Combinatorial Theory Series B",
  "categories": [
    "math.CO"
  ],
  "abstract": "For graphs $G$ and $H$, an $H$-coloring of $G$ is a function from the vertices of $G$ to the vertices of $H$ that preserves adjacency. $H$-colorings encode graph theory notions such as independent sets and proper colorings, and are a natural setting for the study of hard-constraint models in statistical physics. We study the set of $H$-colorings of the even discrete torus ${\\mathbb Z}^d_m$, the graph on vertex set ${0, ..., m-1}^d$ ($m$ even) with two strings adjacent if they differ by 1 (mod $m$) on one coordinate and agree on all others. This is a bipartite graph, with bipartition classes ${\\mathcal E}$ and ${\\mathcal O}$. In the case $m=2$ the even discrete torus is the discrete hypercube or Hamming cube $Q_d$, the usual nearest neighbor graph on ${0,1}^d$. We obtain, for any $H$ and fixed $m$, a structural characterization of the space of $H$-colorings of ${\\mathbb Z}^d_m$. We show that it may be partitioned into an exceptional subset of negligible size (as $d$ grows) and a collection of subsets indexed by certain pairs $(A,B) \\in V(H)^2$, with each $H$-coloring in the subset indexed by $(A,B)$ having all but a vanishing proportion of vertices from ${\\mathcal E}$ mapped to vertices from $A$, and all but a vanishing proportion of vertices from ${\\mathcal O}$ mapped to vertices from $B$. This implies a long-range correlation phenomenon for uniformly chosen $H$-colorings of ${\\mathbb Z}^d_m$ with $m$ fixed and $d$ growing. Our proof proceeds through an analysis of the entropy of a uniformly chosen $H$-coloring, and extends an approach of Kahn, who had considered the special case of $m=2$ and $H$ a doubly infinite path. All our results generalize to a natural weighted model of $H$-colorings.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-06-14T03:28:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "h-coloring tori",
      "colorings encode graph theory notions",
      "discrete torus",
      "usual nearest neighbor graph",
      "uniformly chosen"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1101.0840E"
    }
  }
}