Fast mixing for independent sets, colorings, and other models on trees
From MaRDI portal
Publication:5433255
DOI10.1002/rsa.20132zbMath1138.82020MaRDI QIDQ5433255
Alistair Sinclair, Dror Weitz, Fabio Martinelli
Publication date: 8 January 2008
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20132
phase transitions; Glauber dynamics; mixing time; Markov chain Monte Carlo algorithms; reconstruction on trees
82C20: Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
37A60: Dynamical aspects of statistical mechanics
Related Items
Fuzzy transformations and extremality of Gibbs measures for the potts model on a Cayley tree, Phase Transition of the Reconstructability of a General Model with Different In-Community and Out-Community Mutations on an Infinite Tree, Gibbs measures of Potts model on Cayley trees: A survey and applications, Extremality of some Gibbs measures for the Blume–Capel HC-model on a Cayley tree, Phase transition for the Ising model with mixed spins on a Cayley tree, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Approximate Counting via Correlation Decay in Spin Systems, Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems, Gibbs measures for HC-model with a cuountable set of spin values on a Cayley tree, Inapproximability of counting independent sets in linear hypergraphs, Gibbs periodic measures for a two-state HC-model on a Cayley tree, New class of Gibbs measures for two-state hard-core model on a Cayley tree, Description of the translation-invariant splitting Gibbs measures for the Potts model on a Cayley tree, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Gibbs measures for the fertile three-state hard-core models on a Cayley tree, Extremality of translation-invariant phases for a three-state SOS-model on the binary tree, Reconstruction for the Potts model, On the purity of the free boundary condition Potts measure on random trees, A little statistical mechanics for the graph theorist, Matrix norms and rapid mixing for spin systems, Extremality of the translation-invariant Gibbs measures for the Potts model on the Cayley tree, The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations, Glauber dynamics on trees: Boundary conditions and mixing time, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, Extremality of the unique translation-invariant Gibbs measure for hard-core models on the Cayley tree of order \(k=3\), Reconstructibility of a general DNA evolution model, Extremality of Gibbs measures for the \(HC\)-Blume-Capel model on the Cayley tree, Translation-invariant extreme Gibbs measures for the Blume-Capel model withwand on a Cayley tree, Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects, Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels, Periodic Gibbs measures and their extremes for the HC-Blume-Capel model in the case of a ``wand on the Cayley tree, Randomly coloring constant degree graphs, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, The mixing time of Glauber dynamics for coloring regular trees, Ising model on Cayley trees: a new class of Gibbs measures and their comparison with known ones, Extremality of translation-invariant Gibbs measures for the Potts–SOS model on the Cayley tree, Randomly coloring planar graphs with fewer colors than the maximum degree
Cites Work
