Extending a symmetric one-dependent four-color law across a branch
Let $G$ be the graph with vertices $o, a, b, v_1, v_2, \ldots$ and edges $oa$, $ob$, $ov_1$ and $v_jv_{j+1}$ for $j \ge 1$: a star with three arms, two of length one and one infinite. A random coloring is one-dependent if its restrictions to vertex sets at graph distance greater than one are independent. Holroyd and Liggett constructed a stationary one-dependent proper four-coloring of $\mathbb{Z}$ whose law is invariant under permutations of the colors and under reflection. Liggett and Tang proved that $G$ has no one-dependent four-coloring that is invariant under permutations of the colors and whose restriction to every path is distributed as the Holroyd–Liggett coloring.
Problem. Do there exist a random proper four-coloring $X$ of $G$ and a stationary proper four-coloring $Y = (Y_j)_{j \in \mathbb{Z}}$ of $\mathbb{Z}$ such that both are one-dependent, both laws are invariant under all permutations of the colors, $Y$ is also reflection-invariant, and for every ordered simple path $(w_1, \ldots, w_m)$ in $G$ $$(X_{w_1}, \ldots, X_{w_m}) \overset{\mathrm{law}}{=} (Y_1, \ldots, Y_m)?$$ The line law $Y$ is not required to be the Holroyd–Liggett law.
Source: Liggett and Tang (2023), Section 6, question 1, for the star subgraphs with arms of lengths m, n and ∞; its case m = n = 1, with one common line law, as stated by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, finitely dependent processes, proper colorings, star graphs
References
@article{liggett2023,
author = {Liggett, Thomas M. and Tang, Wenpin},
title = {One-dependent colorings of the star graph},
journal = {Ann. Appl. Probab.},
volume = {33},
number = {6A},
year = {2023},
pages = {4341--4365},
doi = {10.1214/22-AAP1920},
eprint = {1804.06877},
archivePrefix = {arXiv},
}
@article{holroyd2016,
author = {Holroyd, Alexander E. and Liggett, Thomas M.},
title = {Finitely dependent coloring},
journal = {Forum Math. Pi},
volume = {4},
year = {2016},
pages = {e9},
doi = {10.1017/fmp.2016.7},
eprint = {1403.2448},
archivePrefix = {arXiv},
}
@misc{aim-four-color-branched-ray,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Extending a symmetric one-dependent four-color law across a branch}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/584-four-color-branched-ray.md},
note = {Entry 584 at commit a153f46, 2026-10-13},
}
Resolution claims
Let a graph consist of a root, two leaves adjacent to it, and an infinite ray starting at the root. We prove that this graph admits no color-symmetric, one-dependent proper four-coloring whose law on every ordered simple path agrees with a common stationary, reflection-invariant line law. The line law is arbitrary. An infinite color-avoidance recurrence bounds every specified one-step extension …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: AIM @ a153f46, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00748, "Extending a symmetric one-dependent four-color law across a branch", clopen.solutions.