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

DOI10.1007/S00440-009-0222-XzbMATH Open1213.05239arXiv0707.3241OpenAlexW2113610073MaRDI QIDQ5961956FDOQ5961956

Elchanan Mossel, Allan Sly

Publication date: 16 September 2010

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

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.

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

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

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)

Cites Work

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

Cited In (14)

• Randomly coloring planar graphs with fewer colors than the maximum degree
• Spatial mixing and the connective constant: optimal bounds
• The Glauber dynamics for edge‐colorings of trees
• Title not available (Why is that?)
• On the hardness of sampling independent sets beyond the tree threshold
• 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
• Title not available (Why is that?)
• Mixing time of an unaligned Gibbs sampler on the square
• A Spectral Independence View on Hard Spheres via Block Dynamics
• Reconstruction for the Potts model

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)