Coupling with the stationary distribution and improved sampling for colorings and independent sets

DOI10.1214/105051606000000330zbMath1120.60067arXivmath/0610188OpenAlexW2949729746MaRDI QIDQ862206

Eric Vigoda, Thomas P. Hayes

Publication date: 5 February 2007

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

Glauber dynamicsGibbs distributioncoupling methodhard-core modelmixing time of Markov chainsrandom coloringssampling techniquesweighted independent sets

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20)

Related Items (10)

Spatial mixing and the connective constant: optimal bounds ⋮ Randomly coloring planar graphs with fewer colors than the maximum degree ⋮ Spectral independence, coupling, and the spectral gap of the Glauber dynamics ⋮ Phase transition for the mixing time of the Glauber dynamics for coloring regular trees ⋮ Exact thresholds for Ising-Gibbs samplers on general graphs ⋮ Online Edge Coloring via Tree Recurrences and Correlation Decay ⋮ Unnamed Item ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Local uniformity properties for glauber dynamics on graph colorings

Cites Work

• Percolation and the hard-core lattice gas model
• A note on the Glauber dynamics for sampling independent sets
• Improved bounds for sampling colorings
• Randomly coloring constant degree graphs
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Randomly coloring graphs of girth at least five
• Random walks and anO*(n5) volume algorithm for convex bodies
• Randomly coloring graphs with lower bounds on girth and maximum degree
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• Mixing in time and space for lattice spin systems: A combinatorial view
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Coupling with the stationary distribution and improved sampling for colorings and independent sets