More Colors Can Slow Mixing on a Four-Vertex Path
Manuscript 19 October 2026 · Online 19 October 2026
Abstract
Consider the discrete-time coloring chain that chooses a uniform vertex and a uniform color from all q colors, accepting the proposed recoloring when it is proper and otherwise staying in place. On the four-vertex path, the worst-start total-variation mixing time at threshold 1/e equals 8 for q=17 and 9 for q=18. Thus increasing the number of colors can increase the mixing time even on a connected tree with no isolated vertices. We give an exact finite certificate, verified both by full-state integer enumeration and by a color-symmetry quotient. An elementary comparison with independent coordinate refresh also proves that the mixing time is 9 for every q>=512. The result concerns the literal proposal chain and a fixed finite graph, not an asymptotic slowdown on growing lattices. The previously reported edgeless example is credited. This AI-assisted, self-audited preprint is unrefereed and makes no absolute priority claim.
Record
- Affiliation
- Mercury Software GmbH
- Contact
- [email protected] · GitHub
- Result
- Complete connected counterexample
- Categories
- math.PR · math.CO
- Manuscript
- 19 October 2026
- Online release
- 19 October 2026
- Version
- 1.0
- License
- Creative Commons Attribution 4.0 International
Files and verification
The PDF is the canonical reading copy. The source archive contains the LaTeX manuscript, bibliography, reproducibility material, and audit documents without build artefacts.
Citation
Alper Ferudun, “More Colors Can Slow Mixing on a Four-Vertex Path,” EulerSolve Research Papers, AIM-PHYSICS-0025, 2026. https://doi.org/10.5281/zenodo.23461791.
BibTeX
@misc{ferudun2026pathcolormixing,
author = {Ferudun, Alper},
title = {More Colors Can Slow Mixing on a Four-Vertex Path},
year = {2026},
howpublished = {EulerSolve Research Papers},
url = {https://eulersolve.org/papers/aim-physics-0025/},
doi = {10.5281/zenodo.23461791},
note = {AIM-PHYSICS-0025; unrefereed preprint}
}