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

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.