H-coloring tori

Details H-coloring tori H-coloring tori

2011-01-04

arxiv.org/abs/1101.0840v1

Mathematics

Combinatorics

39 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

H-coloring tori 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 H-coloring tori, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and H-coloring tori will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-265775