pith. sign in

arxiv: 2604.11938 · v1 · submitted 2026-04-13 · 💻 cs.DS · cs.DM· math.PR

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity

Vishesh Jain , Clayton Mizgerd , Eric Vigoda This is my paper

Pith reviewed 2026-05-10 14:47 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.PR
keywords graph coloringGlauber dynamicsmixing timeMarkov chainsnon-Markovian couplingapproximate samplinglocal uniformity
0
0 comments X

The pith

The Glauber dynamics mixes in optimal O(n log n) time for k-colorings whenever k is at least (1+δ) times the maximum degree, on graphs with girth at least 11 and sufficiently large Δ.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the Metropolis Glauber dynamics for sampling proper k-colorings of a graph mixes in the optimal O(n log n) steps under stated conditions on k, Δ, and graph structure. It refines an earlier non-Markovian coupling so that proposed updates at one step can depend on and alter proposals at future steps, while adding new local-uniformity guarantees that the coupling succeeds with high probability. A reader would care because the result reaches close to the minimum number of colors needed for any proper coloring and removes the previous restriction to very large degrees.

Core claim

We prove that for every δ>0 and all Δ ≥ Δ0(δ), if k≥ (1+δ)Δ then the Glauber dynamics has optimal mixing time of O_δ(|V| log |V|) on any graph of girth ≥ 11 and maximum degree Δ. The argument develops a refined local non-Markovian coupling for the Metropolis chain and establishes corresponding local-uniformity results that extend prior heat-bath analysis, thereby completing the framework both for the original large-degree regime and for the constant-degree setting.

What carries the argument

The refined local non-Markovian coupling, in which a recoloring proposal at time t may depend on and modify future proposals, together with local-uniformity statements that ensure the coupling succeeds with high probability on high-girth graphs.

If this is right

  • The Glauber dynamics achieves the optimal O(n log n) mixing time in the (1+δ)Δ regime on all high-girth graphs once Δ is large enough.
  • The non-Markovian coupling framework receives a complete analysis that works down to constant maximum degree.
  • Local uniformity of color distributions holds for the Metropolis Glauber dynamics on these graphs, extending the earlier heat-bath results.
  • The gap between the large-degree and constant-degree regimes for this coupling technique is closed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same coupling ideas may extend to other local Markov chains on locally tree-like graphs if analogous uniformity statements can be proved.
  • Removing the girth assumption while keeping the (1+δ)Δ condition would resolve the long-standing open question for arbitrary graphs.
  • The necessity of non-Markovian updates indicates that standard Markovian couplings are unlikely to yield tight bounds near the degree threshold.

Load-bearing premise

The graph must have girth at least 11 so local neighborhoods behave like trees, and the maximum degree must exceed a δ-dependent threshold large enough for the coupling probability to be 1-o(1).

What would settle it

A concrete counter-example would be any family of girth-11 graphs with growing Δ on which the Glauber dynamics requires ω(n log n) steps to mix for k=(1+δ)Δ, or any calculation showing that the non-Markovian coupling fails with constant probability under the same conditions.

Figures

Figures reproduced from arXiv: 2604.11938 by Clayton Mizgerd, Eric Vigoda, Vishesh Jain.

Figure 1
Figure 1. Figure 1: This chain is following the Jerrum coupling. Vertex vt will attempt (blue/red) in the upper and lower chains respectively, leaving it as a (gray/red) discrepancy after time t. vt [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: This chain is following the non-Markovian coupling. By changing past updates, when vt attempts (blue/red) it will remain (gray/gray). We have prevented this discrepancy at the cost of introducing two “temporary” discrepancies in the neighborhood which we have cleverly chosen so that they will be fixed. The color “yellow” is somewhat arbitrary; it encodes that green was the original color of the other verte… view at source ↗
read the original abstract

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 $\Delta$. 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\Delta+2$. We prove that for every $\delta>0$ and all $\Delta \geq \Delta_0(\delta)$, if $k\ge (1+\delta)\Delta$ then the Glauber dynamics has optimal mixing time of $O_{\delta}(|V| \log |V|)$ on any graph of girth $\geq 11$ and maximum degree $\Delta$. Our approach builds on a non-Markovian coupling introduced by Hayes and Vigoda (2003) for the large-degree regime $\Delta=\Omega(\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that for every δ>0 and all sufficiently large Δ≥Δ0(δ), the Metropolis Glauber dynamics for k-colorings mixes in O_δ(n log n) time on any graph with maximum degree Δ and girth at least 11, whenever k≥(1+δ)Δ. The argument refines the non-Markovian coupling of Hayes-Vigoda (2003) to handle the constant-degree regime and establishes new local-uniformity properties for the Metropolis chain that extend Hayes (2013).

Significance. If the central claims hold, the result gives the first optimal mixing time for Glauber dynamics on constant-degree graphs in the regime k=(1+δ)Δ, closing a substantial technical gap in the non-Markovian coupling framework and providing a complete analysis where prior work left obstacles unresolved. The combination of refined coupling and local uniformity is a notable technical contribution.

major comments (2)
  1. [§3.2 and §4.3] §3.2, Definition 3.4 and Lemma 4.7: The local-uniformity statement (each vertex has roughly k-Δ available colors with probability 1-o(1)) is proved for the unmodified Metropolis Glauber transitions. The non-Markovian coupling permits an update at time t to alter proposals at future times; the proof does not explicitly verify that the high-probability uniformity bounds survive these modifications when individual steps fail with constant probability in the constant-degree regime.
  2. [§5.1] §5.1, Equation (12) and the contraction analysis: The coupling inequality used to obtain the O(n log n) mixing bound assumes that the local-uniformity events hold simultaneously for the coupled marginals with probability 1-o(1/n). It is not shown that the failure probability of the refined coupling remains sufficiently small after accounting for the dependencies introduced by future-update modifications.
minor comments (2)
  1. [Theorem 1.1] The dependence of Δ0(δ) on δ is not made explicit; a brief remark on its growth rate would help readers assess the practical range of the result.
  2. [§3 and §4] Notation for the non-Markovian update rule (e.g., the random variables governing proposal modifications) is introduced in §3 but reused without redefinition in §4; a short glossary or consistent indexing would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review and for identifying these subtle points in the analysis of the non-Markovian coupling. We address each major comment below and will revise the manuscript accordingly to clarify the arguments.

read point-by-point responses

  1. Referee: [§3.2 and §4.3] §3.2, Definition 3.4 and Lemma 4.7: The local-uniformity statement (each vertex has roughly k-Δ available colors with probability 1-o(1)) is proved for the unmodified Metropolis Glauber transitions. The non-Markovian coupling permits an update at time t to alter proposals at future times; the proof does not explicitly verify that the high-probability uniformity bounds survive these modifications when individual steps fail with constant probability in the constant-degree regime.

    Authors: The local-uniformity properties are established in a manner that is invariant under the modifications introduced by the non-Markovian coupling. Specifically, the proof of Lemma 4.7 uses a coupling that accounts for the possible alterations to future proposals by showing that such alterations affect only a negligible fraction of the color availability probabilities, even when individual steps fail with constant probability. This is because the high-girth assumption limits the propagation of changes. We acknowledge that this invariance could be stated more explicitly and will add a remark or short paragraph in Section 4.3 to highlight how the bounds survive the non-Markovian updates. revision: yes

  2. Referee: [§5.1] §5.1, Equation (12) and the contraction analysis: The coupling inequality used to obtain the O(n log n) mixing bound assumes that the local-uniformity events hold simultaneously for the coupled marginals with probability 1-o(1/n). It is not shown that the failure probability of the refined coupling remains sufficiently small after accounting for the dependencies introduced by future-update modifications.

    Authors: In the contraction analysis, the failure probability is bounded using a union bound over the n vertices and the O(log n) time steps, with each individual failure probability being o(1/n^2) due to the local nature of the coupling. The dependencies introduced by future modifications are handled by the fact that the coupling is local and the graph has high girth, ensuring that the events are nearly independent. We will expand the discussion around Equation (12) to include a more detailed bound on the overall failure probability that explicitly accounts for these dependencies. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained proof

full rationale

The paper's central result is a new technical analysis establishing local uniformity lemmas for Metropolis Glauber dynamics and a refined non-Markovian coupling that resolves obstacles from prior work. These steps are derived from the dynamics definition and probability bounds on color availability under girth and degree assumptions, without reducing any claimed prediction or mixing-time bound to a fitted parameter, self-definition, or unverified self-citation chain. Self-citations to Hayes-Vigoda 2003 and Hayes 2013 are acknowledged extensions rather than load-bearing premises that close the argument by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard axioms from probability theory and graph theory; no free parameters or invented entities are introduced.

axioms (2)
  • standard math Standard coupling inequalities and total variation distance bounds for Markov chains
    Used to bound mixing time via successful coupling probability.
  • domain assumption Local uniformity properties of colorings under the dynamics on high-girth graphs
    Extended from prior heat-bath results to Metropolis chain.

pith-pipeline@v0.9.0 · 5673 in / 1309 out tokens · 50656 ms · 2026-05-10T14:47:03.429720+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages

  1. [1]

    [BD97] Russ Bubley and Martin E. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. InProceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 223–231, 1997. [CDM+19] Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle. Improved bounds for randomly sampling colorings...

    work page 1997