Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915935185534976 |
|---|---|
| author | Jain, Vishesh Mizgerd, Clayton Vigoda, Eric |
| author_facet | Jain, Vishesh Mizgerd, Clayton Vigoda, Eric |
| contents | Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random $k$-coloring of a graph with maximum degree $Δ$. The simplest algorithmic approach is to establish rapid mixing of the single-site update chain known as the Metropolis Glauber dynamics, which at each step chooses a random vertex $v$ and proposes a random color $c$, recoloring $v$ to $c$ if the resulting coloring remains proper. It is a long-standing open problem to prove that the Glauber dynamics has polynomial mixing time on all graphs whenever $k\geqΔ+2$.
We prove that for every $δ>0$ and all $Δ\geq Δ_0(δ)$, if $k\ge (1+δ)Δ$ then the Glauber dynamics has optimal mixing time of $O_δ(|V| \log |V|)$ on any graph of girth $\geq 11$ and maximum degree $Δ$. Our approach builds on a non-Markovian coupling introduced by Hayes and Vigoda (2003) for the large-degree regime $Δ=Ω(\log n)$, in which updates at time $t$ may depend on and modify proposed updates at future times. A complete analysis of this framework requires resolving substantial technical obstacles that remain in the original argument, and extending it to the constant-degree regime introduces further difficulties, since non-Markovian updates may fail with constant probability.
We overcome these obstacles by developing and analyzing a refined local non-Markovian coupling, and by establishing new local-uniformity results for the Metropolis dynamics, extending prior results for the heat-bath chain due to Hayes (2013). Together, these ingredients provide a complete analysis of the non-Markovian coupling framework in the large-degree regime, while simultaneously strengthening it substantially to obtain optimal mixing all the way down to the constant-degree setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11938 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity Jain, Vishesh Mizgerd, Clayton Vigoda, Eric Data Structures and Algorithms Discrete Mathematics Probability Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random $k$-coloring of a graph with maximum degree $Δ$. The simplest algorithmic approach is to establish rapid mixing of the single-site update chain known as the Metropolis Glauber dynamics, which at each step chooses a random vertex $v$ and proposes a random color $c$, recoloring $v$ to $c$ if the resulting coloring remains proper. It is a long-standing open problem to prove that the Glauber dynamics has polynomial mixing time on all graphs whenever $k\geqΔ+2$. We prove that for every $δ>0$ and all $Δ\geq Δ_0(δ)$, if $k\ge (1+δ)Δ$ then the Glauber dynamics has optimal mixing time of $O_δ(|V| \log |V|)$ on any graph of girth $\geq 11$ and maximum degree $Δ$. Our approach builds on a non-Markovian coupling introduced by Hayes and Vigoda (2003) for the large-degree regime $Δ=Ω(\log n)$, in which updates at time $t$ may depend on and modify proposed updates at future times. A complete analysis of this framework requires resolving substantial technical obstacles that remain in the original argument, and extending it to the constant-degree regime introduces further difficulties, since non-Markovian updates may fail with constant probability. We overcome these obstacles by developing and analyzing a refined local non-Markovian coupling, and by establishing new local-uniformity results for the Metropolis dynamics, extending prior results for the heat-bath chain due to Hayes (2013). Together, these ingredients provide a complete analysis of the non-Markovian coupling framework in the large-degree regime, while simultaneously strengthening it substantially to obtain optimal mixing all the way down to the constant-degree setting. |
| title | Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity |
| topic | Data Structures and Algorithms Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2604.11938 |