Gibbs rapidly samples colorings of \(G(n, d/n)\)

DOI10.1007/s00440-009-0222-xzbMath1213.05239arXiv0707.3241OpenAlexW2113610073MaRDI QIDQ5961956

Elchanan Mossel, Allan Sly

Publication date: 16 September 2010

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

zbMATH Keywords

Gibbs samplingcoloringsErdős--Rényi random graphspolynomial randomized approximation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Monte Carlo methods (65C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Related Items

Spatial mixing and the connective constant: optimal bounds, A Spectral Independence View on Hard Spheres via Block Dynamics, Reconstruction of random colourings, Randomly coloring planar graphs with fewer colors than the maximum degree, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, Unnamed Item, Random sampling of colourings of sparse random graphs with a constant number of colours, Mixing time of an unaligned Gibbs sampler on the square, Reconstruction for the Potts model, Local convergence of random graph colorings, On the hardness of sampling independent sets beyond the tree threshold, The Glauber dynamics for edge‐colorings of trees, A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold, Unnamed Item

Cites Work

• On the hardness of sampling independent sets beyond the tree threshold
• A note on the Glauber dynamics for sampling independent sets
• Glauber dynamics on trees and hyperbolic graphs
• Randomly coloring constant degree graphs
• Counting independent sets up to the tree threshold
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• On Counting Independent Sets in Sparse Graphs
• Approximating the Permanent
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• On Markov Chains for Independent Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item