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

Gibbs samplingcoloringspolynomial randomized approximationErdős--Rényi random graphs

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Random graphs (graph-theoretic aspects) (05C80) 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)

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

• 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?)
• 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
• 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)

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

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)