Hard constraints and the bethe lattice: adventures at the interface of combinatorics and statistical physics TeX Export

@misc{citeulike:2364052, abstract = {Statistical physics models with hard constraints, such as the discrete hard-core gas model (random independent sets in a graph), are inherently combinatorial and present the discrete mathematician with a relatively comfortable setting for the study of phase transition. In this paper we survey recent work (concentrating on joint work of the authors) in which hard-constraint systems are modeled by the space \$\hom(G,H)\$ of homomorphisms from an infinite graph \$G\$ to a fixed finite constraint graph \$H\$. These spaces become sufficiently tractable when \$G\$ is a regular tree (often called a Cayley tree or Bethe lattice) to permit characterization of the constraint graphs \$H\$ which admit multiple invariant Gibbs measures. Applications to a physics problem (multiple critical points for symmetry-breaking) and a combinatorics problem (random coloring), as well as some new combinatorial notions, will be presented.}, archivePrefix = {arXiv}, author = {Brightwell, Graham R. and Winkler, Peter}, citeulike-article-id = {2364052}, citeulike-linkout-0 = {http://arxiv.org/abs/math.CO/0304468}, citeulike-linkout-1 = {http://arxiv.org/pdf/math.CO/0304468}, comment = {* three definitions of phase transition (bimodal distribution, non-unique Gibbs measure, slow mixing of MCMC) * p.609(5) valid colorings as graph homomorphisms}, day = {28}, eprint = {math.CO/0304468}, keywords = {graph-theory, hardcore}, month = {Apr}, posted-at = {2008-02-11 23:18:13}, priority = {2}, title = {Hard constraints and the bethe lattice: adventures at the interface of combinatorics and statistical physics}, url = {http://arxiv.org/abs/math.CO/0304468}, year = {2003} }

TY - ELEC ID - citeulike:2364052 L3 - citeulike-article-id:2364052 N2 - Statistical physics models with hard constraints, such as the discrete hard-core gas model (random independent sets in a graph), are inherently combinatorial and present the discrete mathematician with a relatively comfortable setting for the study of phase transition. In this paper we survey recent work (concentrating on joint work of the authors) in which hard-constraint systems are modeled by the space $\hom(G,H)$ of homomorphisms from an infinite graph $G$ to a fixed finite constraint graph $H$. These spaces become sufficiently tractable when $G$ is a regular tree (often called a Cayley tree or Bethe lattice) to permit characterization of the constraint graphs $H$ which admit multiple invariant Gibbs measures. Applications to a physics problem (multiple critical points for symmetry-breaking) and a combinatorics problem (random coloring), as well as some new combinatorial notions, will be presented. TI - Hard constraints and the bethe lattice: adventures at the interface of combinatorics and statistical physics KW - graph-theory KW - hardcore N1 - * three definitions of phase transition (bimodal distribution, non-unique Gibbs measure, slow mixing of MCMC) * p.609(5) valid colorings as graph homomorphisms AU - Brightwell, Graham AU - Winkler, Peter PY - 2003/Apr/28/ UR - http://arxiv.org/abs/math.CO/0304468 ER -