New weighted Hamming distance yields O(m log n) mixing for Glauber and local flip dynamics on simultaneous edge-colorings when k > (6+δ)Δ and k ≥ 5.95Δ respectively.
A machine-rendered reading of the paper's core claim, the
machinery that carries it, and where it could break.
Two graphs share vertices but have their own edges. A simultaneous edge-coloring assigns colors to all edges so that each graph separately has no two edges at the same vertex sharing a color. The task is to generate a random such coloring uniformly. The authors run Markov chains that repeatedly recolor one edge or flip colors along small connected components. By measuring distance between colorings with a specially weighted version of Hamming distance, they prove these chains reach the uniform distribution after O(m log n) steps once the number of colors is a modest multiple of the maximum degree Δ. The analysis adapts earlier coupling proofs for ordinary edge-coloring to the paired-graph case.
Core claim
Utilizing the flip dynamics with our new metric, we obtain O(m log n) mixing of the flip dynamics with a local choice of flip parameters, which flips only bounded-size components, when k≥5.95Δ.
Load-bearing premise
The coupling analysis with the weighted Hamming distance and local flip parameters extends without additional logarithmic factors or hidden dependencies on graph structure beyond maximum degree Δ; this is invoked when adapting prior flip-dynamics proofs to the simultaneous setting.
read the original abstract
We study the sampling problem for simultaneous edge colorings. Given a pair of graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ which are on the same vertex set $V$, a simultaneous edge coloring is an edge coloring of $G_1\cup G_2$ so that each of the individual graphs is properly colored. When each of $G_1$ and $G_2$ are of maximum degree $\Delta$, then it is conjectured that $\Delta+2$ colors suffice, and recent work asymptotically establishes the conjecture.
We study Markov chains for randomly sampling from the uniform distribution over simultaneous edge colorings. Straightforward applications of Jerrum's classical coupling argument establish rapid mixing of the Glauber dynamics on the corresponding line graph when $k>8\Delta$. We present a simple weighted Hamming distance for which Jerrum's coupling yields optimal mixing time (up to constant factors) of $O(m\log{n})$ when $k>(6+\delta)\Delta$ for any fixed $\delta>0$. Moreover, utilizing the flip dynamics with our new metric, we obtain $O(m\log{n})$ mixing of the flip dynamics with a local choice of flip parameters, which flips only bounded-size components, when $k\geq 5.95\Delta$. The proof adapts previous coupling analyses for the flip dynamics to the setting of simultaneous edge colorings.
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.
The central claims rest on standard probabilistic coupling inequalities and graph-theoretic degree bounds drawn from prior literature; no new free parameters, ad-hoc axioms, or invented entities are introduced.
axioms (2)
standard mathJerrum's coupling argument applies directly to the line graph of the union graph Invoked for the Glauber dynamics baseline when k>8Δ.
domain assumptionGraphs are simple with maximum degree Δ Used to bound the number of colors needed and component sizes in flips.
pith-pipeline@v0.9.0 ·
5553 in / 1347 out tokens ·
51162 ms ·
2026-05-08T15:08:36.547300+00:00
· methodology
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.