Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
From MaRDI portal
Publication:1931316
DOI10.1214/11-AAP833zbMath1266.82043arXiv0908.2665OpenAlexW2763810794WikidataQ58051144 ScholiaQ58051144MaRDI QIDQ1931316
Eric Vigoda, Prasad Tetali, Linji Yang, Juan Carlos Vera
Publication date: 25 January 2013
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0908.2665
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15) Dynamic and nonequilibrium phase transitions (general) in statistical mechanics (82C26)
Related Items
Reconstructibility of a general DNA evolution model ⋮ Randomly coloring planar graphs with fewer colors than the maximum degree ⋮ The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations ⋮ The mixing time of Glauber dynamics for coloring regular trees ⋮ 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 ⋮ Phase Transition of the Reconstructability of a General Model with Different In-Community and Out-Community Mutations on an Infinite Tree ⋮ Randomly coloring constant degree graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reconstruction of random colourings
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Markov chain comparison
- Mixing time of critical Ising model on trees is polynomial in the height
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Uniqueness of uniform random colorings of regular trees
- Glauber dynamics on trees: Boundary conditions and mixing time
- Glauber dynamics on trees and hyperbolic graphs
- A general lower bound for mixing of single-site dynamics on graphs
- Logarithmic Sobolev inequalities for finite Markov chains
- Improved bounds for sampling colorings
- The mixing time of Glauber dynamics for coloring regular trees
- Reconstruction for Colorings on Trees
- The Glauber Dynamics for Colorings of Bounded Degree Trees
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Randomly coloring planar graphs with fewer colors than the maximum degree
- The Glauber Dynamics for Colourings of Bounded Degree Trees
- Randomly coloring graphs with lower bounds on girth and maximum degree
- Balls and bins: A study in negative dependence
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Fast mixing for independent sets, colorings, and other models on trees
- Probability and Computing
- Gibbs rapidly samples colorings of \(G(n, d/n)\)
This page was built for publication: Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
