Uniqueness of the stationary one-dependent four-coloring
A stationary 1-dependent 4-coloring of $\mathbb{Z}$ is a stationary process $X = (X_j)_{j \in \mathbb{Z}}$ with values in $\{1, 2, 3, 4\}$ such that almost surely $X_j \ne X_{j+1}$ for every $j$, and whose restrictions to any two finite sets of indices at distance greater than one are independent. Holroyd and Liggett constructed one, with cylinder probabilities $P_*(x) = \mathbb{P}[(X_1, \dots, X_m) = x]$ for words $x = (x_1, \dots, x_m)$ given by $P_*(\varnothing) = 1$, $P_*(x) = 0$ if two neighbouring symbols of $x$ are equal, and otherwise $$P_*(x) = \frac{1}{2(m+1)} \sum_{j=1}^{m} P_*(x_1, \dots, x_{j-1}, x_{j+1}, \dots, x_m).$$ Its law is invariant under reflection and under permutations of the colors. They showed that every stationary 1-dependent 4-coloring has the same law of $(\mathbf{1}[X_j = 1])_{j \in \mathbb{Z}}$ as this one; and no stationary 1-dependent 3-coloring exists (Schramm; see Holroyd, Schramm and Wilson). Among 4-colorings that are also invariant under reflection and permutations of the colors, the constraints determine the cylinder probabilities of length at most $3$ but leave one free parameter at length $4$ (Liggett and Tang).
Problem. Is every stationary 1-dependent 4-coloring of $\mathbb{Z}$ equal in law to this one? A competing process need not be invariant under reflection or under permutations of the colors.
Source: Holroyd and Liggett (2016), open problem (i), who conjecture that the answer is yes.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, finitely dependent processes, proper colorings
References
@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},
}
@article{holroyd2015,
author = {Holroyd, Alexander E. and Liggett, Thomas M.},
title = {Symmetric 1-dependent colorings of the integers},
journal = {Electron. Commun. Probab.},
volume = {20},
number = {31},
year = {2015},
pages = {1--8},
doi = {10.1214/ECP.v20-4070},
eprint = {1407.4514},
archivePrefix = {arXiv},
}
@article{holroyd2017,
author = {Holroyd, Alexander E. and Schramm, Oded and Wilson, David B.},
title = {Finitary coloring},
journal = {Ann. Probab.},
volume = {45},
number = {5},
year = {2017},
pages = {2867--2898},
doi = {10.1214/16-AOP1127},
}
@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},
}
@misc{aim-one-dependent-four-color-uniqueness,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Uniqueness of the stationary one-dependent four-coloring}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/c9929805cece044705abaaebe1cebddac1ba11a6/problems/588-one-dependent-four-color-uniqueness.md},
note = {Entry 588 at commit c992980, 2026-10-05},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00269, "Uniqueness of the stationary one-dependent four-coloring", clopen.solutions.