  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.
