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 Erd 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 @math . 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 @math . 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 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.
@cite_9: We analyze Markov chains for generating a random k-coloring of a random graph Gn,d n. When the average degree d is constant, a random graph has maximum degree Θ(log n log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k-coloring when k = Θ(log log n log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006
Previous attempts at studying this problem for sampling uniform colorings yielded weaker results. @cite_9 it is shown that Gibbs sampling rapidly mixes on @math if @math where @math and that a variant of the algorithm rapidly mixes if @math . Indeed the main open problem of @cite_9 is to determine if one can take @math to be a function of @math only.