Improved Bounds for Randomly Sampling Colorings via Linear Programming

Sitan Chen, Michelle Delcourt, Ankur Moitra +2

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of $k$-colorings of a graph $G$ on $n$ vertices with maximum degree $\Delta$ is r…