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 (14)

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

This page was built for publication: Gibbs rapidly samples colorings of \(G(n, d/n)\)