## Improved bounds for sampling colorings of sparse random graphs

### With Charis Efthymiou (Frankfurt)

# Improved bounds for sampling colorings of sparse random graphs

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 =>5 and Delta

sufficiently large where alphaapprox 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 $alphaapprox

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.

- Speaker: Charis Efthymiou (Frankfurt)
- Tuesday 28 November 2017, 16:15–17:15
- Venue: MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.
- Series: Probability; organiser: Perla Sousi.