Strong spatial mixing in homomorphism spaces

DOI10.1137/16M1066178MaRDI QIDQ5361232zbMATH OpenFDO

Authors Raimundo Briceño, Ronnie Pavlov

Publication date 27 September 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.01453

zbMATH Keywords

Gibbs measuresgraph homomorphismshard constraintsspatial mixing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: Given a countable graph $mathcalG$ and a finite graph $mathrmH$, we consider $mathrmHom(mathcalG,mathrmH)$ the set of graph homomorphisms from $mathcalG$ to $mathrmH$ and we study Gibbs measures supported on $mathrmHom(mathcalG,mathrmH)$ . We develop some sufficient and other necessary conditions on $mathrmHom(mathcalG,mathrmH)$ for the existence of Gibbs specifications satisfying strong spatial mixing (with exponential decay rate). We relate this with previous work of Brightwell and Winkler, who showed that a graph $mathrmH$ has a combinatorial property called dismantlability if and only if for every $mathcalG$ of bounded degree, there exists a Gibbs specification with unique Gibbs measure. We strengthen their result by showing that this unique Gibbs measure can be chosen to have weak spatial mixing, but we also show that there exist dismantlable graphs for which no Gibbs measure has strong spatial mixing.

Recommendations

• Ergodic theorems on mixing homogeneous spaces
• scientific article; zbMATH DE number 1461830
• Strong spatial mixing for repulsive point processes
• Homogenisation on homogeneous spaces
• Spatial mixing and the connective constant: optimal bounds
• Spatial mixing and the connective constant: optimal bounds
• Strong mixing measures for \(C_0\)-semigroups
• On mixing and sparse ergodic theorems
• Strongly mixing transformations and geometric diameters
• Strong local homogeneity and coset spaces

Cites work

• A new lower bound for the critical probability of site percolation on the square lattice
• An integral representation for topological pressure in terms of conditional probabilities
• Combinatorial criteria for uniqueness of Gibbs measures
• Computing bounds for entropy of stationary \(\mathbb{Z}^d\) Markov random fields
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Correlation decay up to uniqueness in spin systems
• Counting independent sets up to the tree threshold
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Disagreement percolation in the study of Markov fields
• For 2-D lattice spin systems weak mixing implies strong mixing
• Gibbs measures and dismantlable graphs
• Gibbs measures and phase transitions.
• Graph homomorphisms and phase transitions
• scientific article; zbMATH DE number 193132 (Why is no real title available?)
• scientific article; zbMATH DE number 2019625 (Why is no real title available?)
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Incidence matrices and interval graphs
• Mixing in time and space for lattice spin systems: A combinatorial view
• One-dimensional Markov random fields, Markov chains and topological Markov fields
• Representation and poly-time approximation for pressure of Z^2 lattice models in the non-uniqueness region
• Sequential cavity method for computing free energy and surface pressure
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
• Vertex-to-vertex pursuit in a graph

Cited in

(14)

• Graph homomorphisms and phase transitions
• Gibbs measures and dismantlable graphs
• Mixing properties for hom-shifts and the distance between walks on associated graphs
• Strong spatial mixing for repulsive point processes
• Dismantlability, connectedness, and mixing in relational structures
• An SMB approach for pressure representation in amenable virtually orderable groups
• The topological strong spatial mixing property and new conditions for pressure approximation
• Mixing properties of colourings of the ℤ^d lattice
• Self-stabilisation of Cellular Automata on Tilings
• Dismantlability, Connectedness, and Mixing in Relational Structures
• Absence of zeros implies strong spatial mixing
• Short-range and long-range order: a transition in block-gluing behavior in Hom shifts
• Undecidability of the block gluing classes of homshifts
• Finitary codings for spatial mixing Markov random fields

This page was built for publication: Strong spatial mixing in homomorphism spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361232)