✦ LIBER ✦

Graph Homomorphisms and Phase Transitions

✍ Scribed by Graham R. Brightwell; Peter Winkler

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 627 KB
Volume: 77
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1999.1899

No coin nor oath required. For personal study only.

✦ Synopsis

We model physical systems with ``hard constraints'' by the space Hom(G, H) of homomorphisms from a locally finite graph G to a fixed finite constraint graph H. For any assignment * of positive real activities to the nodes of H, there is at least one Gibbs measure on Hom(G, H); when G is infinite, there may be more than one. When G is a regular tree, the simple, invariant Gibbs measures on Hom(G, H) correspond to node-weighted branching random walks on H. We show that such walks exist for every H and *, and characterize those H which, by admitting more than one such construction, exhibit phase transition behavior.

📜 SIMILAR VOLUMES

Independence and graph homomorphisms gra

Independence and graph homomorphisms graph homomorphisms

✍ Michael O. Albertson; Lily Chan; Ruth Haas 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 305 KB

## Abstract A graph with __n__ vertices that contains no triangle and no 5‐cycle and minimum degree exceeding __n__/4 contains an independent set with at least (3__n__)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7‐cycle and invoking the No Homomorphism

On homomorphic images of transition grap

On homomorphic images of transition graphs

✍ Michael Yoeli; Abraham Ginzburg 📂 Article 📅 1964 🏛 Elsevier Science 🌐 English ⚖ 296 KB

Geometric graph homomorphisms

✍ Debra L. Boutin; Sally Cockburn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract A __geometric graph__ is a simple graph drawn on points in the plane, in general position, with straightline edges. A __geometric__ __homomorphism__ from to is a vertex map that preserves adjacencies and crossings. This work proves some basic properties of geometric homomorphisms and

Graph homomorphisms and nodal domains

✍ Amir Daneshgar; Hossein Hajiabolhassan 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 137 KB

In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adj

Graph homomorphisms through random walks

✍ Amir Daneshgar; Hossein Hajiabolhassan 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract In this paper we introduce some general necessary conditions for the existence of graph homomorphisms, which hold in both directed and undirected cases. Our method is a combination of Diaconis and Saloff–Coste comparison technique for Markov chains and a generalization of Haemers interl

Path homomorphisms, graph colorings, and

Path homomorphisms, graph colorings, and boolean matrices

✍ Jaroslav Nešetřil; Claude Tardif 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract We investigate bounds on the chromatic number of a graph __G__ derived from the nonexistence of homomorphisms from some path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray\*}\vec{P}\end{eqnarray\*}\end{document} into some orientation \documentclass{