Gibbs rapidly samples colorings of G(n, d/n)
From MaRDI portal
(Redirected from Gibbs rapidly samples colorings of G(n, d/n))
Gibbs rapidly samples colorings of \(G(n, d/n)\)
Gibbs rapidly samples colorings of \(G(n, d/n)\)
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 . 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 . 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 there exists such that for all the mixing time of Gibbs sampling on G(n,d/n) is polynomial in 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.
The paper studies so-called Gibb's sampling, a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erdős--Rényi random graph \(G(n; d/n)\), where each edge is chosen independently with probability \(d/n\), \(d\) is fixed. The authors give the first rapid convergence result of Gibbs samplers for the coloring model on Erdős--Rényi random graphs in terms of the average degree and the number of colors only. These results yield the first fully polynomial randomized approximation scheme for sampling the coloring distribution in this case. Some related works and a sketch of the proof are given in the introduction. The remaining sections give a more detailed proof.
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)
