Document Type

Article

Language

eng

Format of Original

24 p.

Publication Date

9-2012

Publisher

Elsevier

Source Publication

Journal of Combinatorial Theory, Series B

Source ISSN

0095-8956

Original Item ID

doi: 10.1016/j.jctb.2012.05.003

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 View the MathML source, 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 Qd, 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 View the MathML source. 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)∈V(H)2, with each H-coloring in the subset indexed by (A,B) having all but a vanishing proportion of vertices from E 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 View the MathML source with m fixed and d growing. The special pairs (A,B)∈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 View the MathML source, that in a uniformly chosen H-coloring f of View the MathML source the pair View the MathML source 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.

Comments

Accepted version. Journal of Combinatorial Theory, Series B, Vol. 102, No. 5 (September, 2012): 1110-1133. DOI.

NOTICE: this is the author’s version of a work that was accepted for publication in Journal of Combinatorial Theory, Series B. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in the Journal of Combinatorial Theory, Series B, VOL 102, ISSUE 5, (September 2012) DOI.

Download

Share

COinS