English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A well-known conjecture in computer science and statistical physics is thatGlauber dynamics on the set of $k$-colorings of a graph $G$ on $n$ verticeswith maximum degree $\Delta$ is rapidly mixing for $k \geq \Delta +2$. In FOCS1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameterson the set of proper $k$-colorings for $k > \frac{11}{6}\Delta$, implying rapidmixing for Glauber dynamics. In this paper, we obtain the first improvementbeyond the $\frac{11}{6}\Delta$ barrier for general graphs by showing rapidmixing for $k > (\frac{11}{6} - \eta)\Delta$ for some positive constant $\eta$.The key to our proof is combining path coupling with a new kind of metric thatincorporates a count of the extremal configurations of the chain. Additionally,our results extend to list coloring, a widely studied generalization ofcoloring. Combined, these results answer two open questions from Frieze andVigoda's 2007 survey paper on Glauber dynamics for colorings.

Rapid mixing of Glauber dynamics for colorings below Vigoda's $11/6$ threshold