Gibbs measures and dismantlable graphs.

*(English)*Zbl 1030.05101Summary: We model physical systems with “hard constraints” by the space \(\operatorname{Hom}(G,H)\) of homomorphisms from a locally finite graph \(G\) to a fixed finite constraint graph \(H\). Two homomorphisms are deemed to be adjacent if they differ on a single site of \(G\). We investigate what appears to be a fundamental dichotomy of constraint graphs, by giving various characterizations of a class of graphs that we call dismantlable. For instance, \(H\) is dismantlable if and only if, for every \(G\), any two homomorphisms from \(G\) to \(H\) which differ at only finitely many sites are joined by a path in \(\operatorname{Hom}(G, H)\). If \(H\) is dismantlable, then, for any \(G\) of bounded degree, there is some assignment of activities to the nodes of \(H\) for which there is a unique Gibbs measure on \(\operatorname{Hom}(G, H)\). On the other hand, if \(H\) is not dismantlable (and not too trivial), then there is some \(r\) such that, whatever the assignment of activities on \(H\), there are uncountably many Gibbs measures on \(\operatorname{Hom}(T_r,H)\), where \(T_r\) is the \((r+ 1)\)-regular tree.

##### MSC:

05C75 | Structural characterization of families of graphs |

60C05 | Combinatorial probability |

60K35 | Interacting random processes; statistical mechanics type models; percolation theory |

82B05 | Classical equilibrium statistical mechanics (general) |

82B20 | Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics |

PDF
BibTeX
XML
Cite

\textit{G. R. Brightwell} and \textit{P. Winkler}, J. Comb. Theory, Ser. B 78, No. 1, 141--166 (2000; Zbl 1030.05101)

Full Text:
DOI

##### References:

[1] | Bandelt, H.-J.; Mulder, H.M., Helly theorems for dismantlable graphs and pseudo-modular graphs, Topics in combinatorics and graph theory (oberwolfach, 1990), (1990), Physica Heidelberg, p. 65-71 · Zbl 0697.05034 |

[2] | van den Berg, J., A uniqueness condition for Gibbs measures with application to the 2-dimensional Ising antiferromagnet, Comm. math. phys., 152, 161-166, (1993) · Zbl 0768.60098 |

[3] | van den Berg, J.; Steif, J.E., Percolation and the hard-core lattice gas model, Stochastic proc. and their appls., 49, 179-197, (1994) · Zbl 0787.60125 |

[4] | G. Brightwell, and, P. Winkler, Graph homomorphisms and phase transitions, J. Comb. Theory Series B, to appear. · Zbl 1026.05028 |

[5] | Dobrushin, P.L., The description of a random field by means of conditional probabilities and conditions of its regularity, Thy. of prob. and its appls., 13, 197-224, (1968) |

[6] | Georgii, H.-O., Gibbs measures and phase transitions, (1988), de Gruyter Berlin · Zbl 0657.60122 |

[7] | Hell, P.; Nešetřil, J., The core of a graph, Disc. math., 109, 117-126, (1992) · Zbl 0803.68080 |

[8] | Kelly, F.P., Stochastic models of computer communication systems, J. R. statist. soc. B, 47, 379-395, (1985) · Zbl 0592.68029 |

[9] | Nowakowski, R.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete math., 43, 235-239, (1983) · Zbl 0508.05058 |

[10] | Polat, N., A Helly theorem for geodesic convexity in strongly dismantlable graphs, Disc. math., 140, 119-127, (1995) · Zbl 0828.05062 |

[11] | A. Quilliot, Homomorphismes, points fixes, rétractions et jeux de poursuite dans les graphes, les ensembles ordonnés et les espaces métriques, Thèse d’Etat, Université de Paris VI, Paris, France, 1983. |

[12] | Widom, B.; Rowlinson, J.S., New model for the study of liquid-vapor phase transition, J. chem. phys., 52, 1670-1684, (1970) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.