2018/04/11 by Michelle Delcourt, Guillem Perarnau, Delcourt, Michelle +3
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.1804.04025
openalex publication_date 2018/04/11 · openalex created_date 2018/04/24 · openalex updated_date 2026/07/28
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 Δ is rapidly mixing for k ≥ Δ+2. In FOCS 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper k-colorings for k > (11)/(6)Δ, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the (11)/(6)Δ barrier for general graphs by showing rapid mixing for k > ((11)/(6) - η)Δ for some positive constant η. The key to our proof is combining path coupling with a new kind of metric that incorporates a count of the extremal configurations of the chain. Additionally, our results extend to list coloring, a widely studied generalization of coloring. Combined, these results answer two open questions from Frieze and Vigoda's 2007 survey paper on Glauber dynamics for colorings.