Source-linked AI summary
Sampling Line-Graph Colorings with Constant Extra Colors
Alireza Haqi
TL;DR
Uniformly sampling proper colorings is a fundamental approximate-counting problem, and the key question is how many colors let single-site Glauber dynamics converge quickly from every proper initial coloring. Using a discrete Bochner approach, the paper proves an O_Δ(n log(n/ε)) mixing bound for line graphs when q ≥ Δ + 5.
Problem
How many colors suffice for single-site Glauber dynamics to converge quickly from every proper initial coloring, a fundamental problem in approximate counting and Markov chain algorithms?
Source: §1 · p. 1Method
A discrete Bochner method gives a finite-sum identity for uniform coloring measures, uses an unsigned incidence matrix for line graphs, and derives conditional Poincaré inequalities before applying the entropy theorem of Chen, Liu, and Vigoda [CLV26, Theorem 1.12].
Source: §1.2 · p. 2Results
For line graphs and q ≥ Δ + 5, single-site Glauber dynamics for proper q-colorings mixes in O_Δ(n log(n/ε)) steps.
Source: §1.1 · pp. 1–2, §6 · p. 9Takeaways & Limitations
For line graphs, the rapid-mixing color threshold is three colors above the Δ + 2 threshold in the bounded-degree coloring conjecture.
Source: §1 · p. 1, §1.1 · p. 2The mixing time for q = Δ + 2 remains open, and the proof’s estimate at q = Δ + 4 gives only a zero lower bound, not a counterexample to rapid mixing.
Source: §7 · p. 9
Abstract
from arXiv · showhide
Let $G$ be the line graph of a finite simple graph, with $n\geq1$ vertices and maximum degree $\Delta$. We prove that single-site Glauber dynamics for uniform proper $q$-colorings mixes in $O_\Delta(n\log(n/\varepsilon))$ steps for every integer $q\geq\Delta+5$. Our proof uses the Bochner framework of Chen and Liu (2026).
1 Introduction
The paper proves rapid Glauber mixing for proper colorings of line graphs at a palette threshold of Δ+5, and develops a Bochner-based route from conditional variance bounds to mixing. This replaces a degree-dependent palette surplus in prior line-graph bounds with an additive constant, while leaving stronger spatial-mixing claims outside its scope.
1 Introduction
- The bounded-degree coloring-dynamics conjecture asks for polynomial mixing whenever q≥Δ+2, whereas this paper studies the restricted class of line graphs.Proper vertex colorings of a line graph correspond to proper edge colorings of its root graph.Source: §1 · p. 1
1.2 Prior work
- Theorem 2 replaces the degree-dependent palette surplus in the prior line-graph bound with the additive constant five.The prior bound is q≥Δ+O(Δ/log Δ) for Δ>1 [WZZ24, Theorem 1].Source: §1.2 · p. 2
- The Bochner approach gives spectral independence from conditional Poincaré inequalities, then uses the entropy theorem of Chen, Liu, and Vigoda [CLV26, Theorem 1.12] to obtain n log n mixing.The line-graph structure enters through an unsigned incidence matrix.Source: §1.2 · p. 2
- The proof makes no claim of strong spatial mixing or deterministic approximate counting, which concern properties distinct from the Glauber bounds proved here.The cited related work studies coupling independence and spatial mixing for edge colorings.Source: §1.2 · p. 2
1.3 Proof overview
- For line graphs, the unsigned incidence matrix yields a spectral-gap lower bound of q−Δ−4, which transfers to conditional Glauber chains after feasible pinnings.The conditional gap is at least (q−Δ−4)/(kq) when k vertices remain unpinned.Source: §1.3 · p. 3
- The proof combines uniform-in-q mixing parameters for Δ+5≤q≤2Δ with Jerrum’s coupling for q≥2Δ+1 to obtain O_Δ(n log(n/ε)) mixing for q≥Δ+5.The lower bound on one-vertex marginals permits use of the entropy theorem of Chen, Liu, and Vigoda [CLV26].Source: §1.3 · p. 3
2 Preliminaries
The preliminaries set conventions for coloring measures and Glauber operators, then state an integrated Bochner criterion for proving spectral gaps. They also connect a projection-based criterion to the paper’s line-graph Bochner identity.
2.1 Coloring measures and Markov chain conventions
- The notation distinguishes line-graph vertices, which represent root-graph edges, from root-graph vertices used in the edge-coloring argument.The mixing-time convention counts individual updates; fully pinned configurations have mixing time zero.Source: §2.1 · pp. 3–4
- A proper list-coloring space is sampled uniformly, and the update at a vertex averages over its feasible colors while other vertices stay fixed.The constant-rate Laplacian uses rate one for each feasible recoloring, and its Dirichlet form is built from the conditional variances.Source: §2.1 · pp. 3–4
2.2 The integrated Bochner criterion
- The integrated Bochner criterion converts an operator inequality comparing the squared generator with the generator into a spectral-gap bound.The criterion assumes a self-adjoint positive semidefinite operator whose kernel consists exactly of constants.Source: §2.2 · p. 4
2.3 The projection framework of Chen and Liu [CL26b]
- Chen and Liu’s spectral-influence criterion gives gap(P_GL) ≥ ε/n for an irreducible Glauber chain when a symmetric, nonnegative, zero-diagonal cross-term matrix has maximum eigenvalue at most 1−ε (0<ε<1).They derive the cross-term bounds from two-coordinate conditional walks [CL26b, Theorem 1.2 and Corollary 3.2].Source: §2.3 · p. 5
- For line graphs, the paper’s identity bounds the squared constant-rate Laplacian below by (m−4) times the Laplacian when every feasible-color count is at least m.A Dirichlet-form comparison then transfers the bound to the Glauber gap.Source: §2.3 · p. 5
3 An exact Bochner identity for recolorings
The section expands the squared gradient into diagonal terms, contributions from recoloring squares, and incompatible moves. For line graphs, an unsigned incidence-matrix bound yields a Bochner certificate from lower bounds on feasible-color counts.
3.1 Squares and incompatible moves
- A jointly feasible pair of nontrivial recolorings forms a square of four configurations with the same pinning outside the two recolored vertices.The alternating sum compares the change from recoloring one vertex before and after recoloring the other; its square is independent of starting corner or order.Source: §3.1 · p. 5
- The square contributions count each four-configuration set once, while the two vertex orderings supply a factor of two in the identity.The expansion also separates diagonal terms from cross terms.Source: §3.1 · pp. 5–6
- Jointly improper recolorings can occur only when the vertices are adjacent and both moves assign them the same color.The incidence-matrix bound for line graphs is used to bound the resulting collision term from below.Source: §3 · p. 5, §3.1 · p. 6, §3.2 · p. 7
3.2 The incidence certificate for line graphs
- Theorem 5 bounds the Dirichlet form by the expected one-site variances when every edge has at least m feasible colors.The certificate applies to every function on a nonempty proper edge-list-coloring space of a line graph.Source: §3.2 · p. 7
4 Spectral gaps
The section converts the line-graph Bochner certificate into spectral-gap bounds, using connectivity of the coloring space. The bounds apply uniformly after feasible pinnings, including when residual graphs are disconnected.
4 Spectral gaps
- When every vertex has at least its degree plus two colors in its list, proper list-colorings exist and any two are connected by feasible single-vertex recolorings.This fact supplies connectivity for the coloring spaces after pinning.Source: §4 · p. 7
- For a line graph with nonempty connected coloring space and at least m>4 feasible colors at every vertex, Corollary 7 gives a spectral-gap bound.The proof uses connectivity to restrict the kernel of the generator to constant functions, then applies the Bochner certificate.Source: §4 · p. 7
- Under q≥Δ+5, each conditional model retains at least m=q−Δ feasible colors per remaining vertex and has a connected coloring space.The residual graph remains a line graph after deleting the root-graph edges corresponding to pinned vertices, so Corollary 7 applies uniformly over pinnings.Source: §4 · p. 7
- The gap statements in Theorem 2 follow from the preceding equation, and residual graphs need not be connected for the coloring-space connectivity argument.The coloring spaces of the residual graphs are the relevant setting for the connectivity argument.Source: §4 · p. 8
5 Spectral independence
The section defines conditional influence matrices and uses a Glauber-gap bound to obtain a spectral-independence bound under every feasible pinning.
5 Spectral independence
- The spectral-independence conclusion follows by applying the universality theorem with C=q/κ to the spectral-gap bound from Section 4.The influence matrix convention in this section uses the centered correlation matrix I+Ψτ.Source: §5 · p. 8
- For every feasible pinning, Corollary 8 bounds the largest eigenvalue of the conditional influence matrix under Theorem 2’s assumptions.The matrix is indexed by vertex-color pairs of positive marginal probability; its off-site entries are conditional-minus-marginal probabilities and its within-vertex blocks are zero.Source: §5 · p. 8
- The influence bound holds conditionally under every feasible pinning, not only for the unconditioned coloring measure.Source: §5 · p. 8
6 Entropy and mixing with a uniform palette bound
The section applies an entropy theorem to proper colorings after verifying its hypotheses, and combines that approach with a classical coupling bound to address palette sizes beyond the interval treated by the theorem. The proof also derives a one-vertex marginal lower bound and uses spectral mixing estimates; the supplied theorem-dependence remark notes a doubly exponential bound on the mixing constant in Δ.
6 Entropy and mixing with a uniform palette bound
- For any feasible pinning, the proof bounds the chance that a specified color remains available at a vertex by first bounding the chance that its unpinned neighbors avoid that color.The neighbor-avoidance probability is at least (1 − 1/m)^ℓ; when the color is available, its conditional probability at the vertex is at least 1/q.Source: §6 · pp. 8–9
- The proof uses the spectral-gap and influence bounds, the nonnegative spectrum of the Glauber operator, and a standard spectral mixing estimate to obtain a second mixing bound.Taking the stated ceiling in Equation (1.1) makes the bound at most ε.Source: §6 · p. 9
- The entropy theorem’s hypotheses are verified for proper colorings, yielding O_Δ,q(n log(n/ε)) mixing; the proof then treats Δ + 5 ≤ q ≤ 2Δ to make the mixing constant independent of q.For q ≥ 2Δ + 1, Jerrum’s coupling gives O_Δ(n log(n/ε)) mixing uniformly in q.Source: §6 · p. 9
- Theorem 2’s constant C_Δ is bounded by exp(exp(O(Δ))) in this proof, while the optimal dependence on Δ may be smaller.The stated bound follows by substituting Equation (6.3) into the quantitative estimate of Chen–Liu–Vigoda [CLV26, Theorem 1.12].Source: §6 · p. 9
7 Limitations and further questions
The section identifies limits of the available estimate and leaves two questions open: the mixing time at q = Δ + 2 and the optimal dependence of the mixing constant on Δ.
7 Limitations and further questions
- At q = Δ + 4, the factor-four estimate gives only a zero lower bound; this is a limitation of the estimate, not a counterexample to rapid mixing.The mixing time for q = Δ + 2 and the optimal dependence of C_Δ remain open.Source: §7 · p. 9