H-coloring tori

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 Z(m)(d), 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 E and 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 Z(m)(d). 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) is an element of V (H)(2), with each H-coloring in the subset indexed by (A, B) having all but a vanishing proportion of vertices from epsilon mapped to vertices from A, and all but a vanishing proportion of vertices from O mapped to vertices from B. This implies a long-range correlation phenomenon for uniformly chosen H-colorings of Z(m)(d) with m fixed and d growing. The special pairs (A, B) is an element of V(H)(2) are characterized by every vertex in A being adjacent to every vertex in B, and having |A||B| maximal subject to this condition. Our main technical result is an upper bound on the probability, for an arbitrary edge uv of Z(m)(d), that in a uniformly chosen H-coloring f of Z(m)(d) the pair ({f(w): w is an element of N-u}, {f(z): z is an element of N-v}) is not one of these special pairs (where N. indicates neighborhood). Our proof proceeds through an analysis of the entropy of f, and extends an approach of Kahn. who had considered the case of m = 2 and H a doubly infinite path. All our results generalize to a natural weighted model of H-colorings. (C) 2012 Elsevier Inc. All rights reserved.