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

DOI10.1007/S00440-009-0222-XMaRDI QIDQ5961956zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel, Allan Sly

Publication date 16 September 2010

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 2.0 Generic

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

zbMATH Keywords

coloringsErdős--Rényi random graphsGibbs samplingpolynomial randomized approximation

Mathematics Subject Classification ID

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

Abstract: Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the ErdH{o}s-R'enyi random graph G(n,d/n). While the average degree in G(n,d/n) is d(1-o(1)), it contains many nodes of degree of order $logn/loglogn$. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring or the Ising model, the mixing time of Gibbs sampling is at least $n^{1+Omega(1/loglogn)}$. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. In this work consider sampling q-colorings and show that for every $d<infty$ there exists $q(d)<infty$ such that for all $qgeqq(d)$ the mixing time of Gibbs sampling on G(n,d/n) is polynomial in $n$ with high probability. Our results are the first polynomial time mixing results proven for the coloring model on G(n,d/n) for d > 1 where the number of colors does not depend on n. They extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.

Recommendations

• Switching colouring of G(n,d/n) for sampling up to Gibbs uniqueness threshold
• A Simple Algorithm for Sampling Colorings of G(n,d/n) Up to The Gibbs Uniqueness Threshold
• MCMC sampling colourings and independent sets of \(G(n, d/n)\) near uniqueness threshold
• Sampling random colorings of sparse random graphs
• Rapid mixing of Gibbs sampling on graphs that are sparse on average

Cites work

• A note on the Glauber dynamics for sampling independent sets
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Approximating the Permanent
• Counting independent sets up to the tree threshold
• Glauber dynamics on trees and hyperbolic graphs
• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• scientific article; zbMATH DE number 5764879 (Why is no real title available?)
• scientific article; zbMATH DE number 1188961 (Why is no real title available?)
• scientific article; zbMATH DE number 1418384 (Why is no real title available?)
• On Counting Independent Sets in Sparse Graphs
• On Markov Chains for Independent Sets
• On the hardness of sampling independent sets beyond the tree threshold
• Randomly coloring constant degree graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces

Cited in

(22)

• On the hardness of sampling independent sets beyond the tree threshold
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Mixing time of an unaligned Gibbs sampler on the square
• Spatial mixing and the connective constant: optimal bounds
• Local uniformity properties for Glauber dynamics on graph colorings
• Switching colouring of G(n,d/n) for sampling up to Gibbs uniqueness threshold
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• The Glauber dynamics for edge-colorings of trees
• Sampling random colorings of sparse random graphs
• Sampling in Potts model on sparse random graphs
• Randomly coloring graphs of logarithmically bounded pathwidth
• A spectral independence view on hard spheres via block dynamics
• MCMC sampling colourings and independent sets of \(G(n, d/n)\) near uniqueness threshold
• A Simple Algorithm for Sampling Colorings of G(n,d/n) Up to The Gibbs Uniqueness Threshold
• A simple algorithm for random colouring G(n, d/n) using (2 + )d colours
• Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
• Reconstruction for the Potts model
• Local convergence of random graph colorings
• A spectral independence view on hard spheres via block dynamics
• Reconstruction of random colourings
• Random sampling of colourings of sparse random graphs with a constant number of colours

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961956)