Improved bounds for sampling colorings of sparse random graphs

Add to your list(s) Download to your calendar using vCal

• Charis Efthymiou (Frankfurt)
• Tuesday 28 November 2017, 16:15-17:15
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact Perla Sousi.

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>11\Delta/6 for all G. Improved results hold when k>\alpha\Delta for graphs with girth =>5 and \Delta sufficiently large where \alpha\approx 1.7632… 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>\alpha d where $\alpha\approx 1.7632… 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.

This is a joint work with Tom Hayes, Daniel Stefankovic and Eric Vigoda.

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.