Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e) delta via Hidden Hard-Core Models
cs.DS, cs.DM, math.CO, math.PR
Submitted: 2026-11-03
Updated: 2026-11-03
Terminology
Sources
- A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five
- An FPRAS for Counting Common Bases of Two Matroids
- A simple proof of rapid mixing on random regular graphs beyond uniqueness
- Approximating spin systems on planar graphs
- Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
- Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
- Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time