Sampling random colorings of sparse random graphs

MaRDI QIDQ4608004zbMATH OpenFDO

Authors Charilaos Efthymiou, Thomas P. Hayes, D. Štefankovič, Eric Vigoda

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1707.03796, http://dl.acm.org/citation.cfm?id=3175420

zbMATH Keywords

block dynamicsGlauber dynamics

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the mixing properties of the single-site Markov chain known as the Glauber dynamics for sampling $k$-colorings of a sparse random graph $G(n,d/n)$ for constant $d$. The best known rapid mixing results for general graphs are in terms of the maximum degree $Delta$ of the input graph $G$ and hold when $k>11Delta/6$ for all $G$. Improved results hold when $k>alphaDelta$ for graphs with girth $geq5$ and $Delta$ sufficiently large where $alphaapprox1.7632ldots$ is the root of $alpha=exp(1/alpha)$; further improvements on the constant $alpha$ hold with stronger girth and maximum degree assumptions. For sparse random graphs the maximum degree is a function of $n$ and the goal is to obtain results in terms of the expected degree $d$. The following rapid mixing results for $G(n,d/n)$ hold with high probability over the choice of the random graph for sufficiently large constant~$d$. Mossel and Sly (2009) proved rapid mixing for constant $k$, and Efthymiou (2014) improved this to $k$ linear in~$d$. The condition was improved to $k>3d$ by Yin and Zhang (2016) using non-MCMC methods. Here we prove rapid mixing when $k>alphad$ where $alphaapprox1.7632ldots$ is the same constant as above. Moreover we obtain $O(n^3)$ mixing time of the Glauber dynamics, while in previous rapid mixing results the exponent was an increasing function in $d$. As in previous results for random graphs our proof analyzes an appropriately defined block dynamics to "hide" high-degree vertices. One new aspect in our improved approach is utilizing so-called local uniformity properties for the analysis of block dynamics. To analyze the "burn-in" phase we prove a concentration inequality for the number of disagreements propagating in large blocks.

Recommendations

• scientific article; zbMATH DE number 5279368
• Randomly coloring graphs of girth at least five
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Randomly coloring constant degree graphs
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

Cited in

(31)

• Constraining the clustering transition for colorings of sparse random graphs
• Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings
• Uniqueness for the 3-state antiferromagnetic Potts model on the tree
• Local uniformity properties for Glauber dynamics on graph colorings
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• Maximum Weight Partial Colorings on Sparse Random Graphs
• The Glauber dynamics for edge-colorings of trees
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• Sampling in Potts model on sparse random graphs
• Deterministic counting of graph colourings using sequences of subgraphs
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• A spectral independence view on hard spheres via block dynamics
• Counting solutions to random CNF formulas
• Spatial mixing of coloring random graphs
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Improved bounds for randomly sampling colorings via linear programming
• MCMC sampling colourings and independent sets of \(G(n, d/n)\) near uniqueness threshold
• On sampling colorings of bipartite graphs
• A Simple Algorithm for Sampling Colorings of G(n,d/n) Up to The Gibbs Uniqueness Threshold
• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Rapid Mixing from Spectral Independence beyond the Boolean Domain
• Rapid mixing from spectral independence beyond the Boolean domain
• Counting solutions to random CNF formulas
• Fast sampling via spectral independence beyond bounded-degree graphs
• A spectral independence view on hard spheres via block dynamics
• Low-temperature sampling on sparse random graphs
• Low-temperature sampling on sparse random graphs
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Random sampling of colourings of sparse random graphs with a constant number of colours

This page was built for publication: Sampling random colorings of sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608004)