OP-00768 Solution claimed

Automorphism-invariant one-dependent colorings of regular trees

Let $T_d = (V, E)$ be the infinite $d$-regular tree, $d \ge 3$. A random field $X = (X_v)_{v \in V}$ with values in $\{1, \dots, q\}$ is a proper coloring if almost surely $X_u \ne X_v$ for every edge $uv \in E$, and is one-dependent if $X|_A$ and $X|_B$ are independent for any two finite sets $A, B \subset V$ at graph distance greater than one. Holroyd and Liggett constructed a stationary one-dependent proper $4$-coloring of $\mathbb{Z}$, the case $d = 2$, and for each $q \ge 4$ a stationary one-dependent proper $q$-coloring of $\mathbb{Z}$ whose law is invariant under reflection and under permutations of the colors. Timár constructed, on every unimodular transitive graph of maximal degree $d$, and so on $T_d$, an automorphism-invariant two-dependent proper coloring with $3^{d(d+1)/2}$ colors. A one-dependent proper coloring of $T_d$ whose law is invariant under its automorphisms uses at least $d^d/(d-1)^{d-1}$ colors (see Liggett and Tang).

Problem. For each $d \ge 3$, is there a finite integer $q = q(d)$ and a one-dependent proper coloring $X \in \{1, \dots, q\}^V$ of $T_d$ whose law is invariant under every automorphism of $T_d$ and under every permutation of the $q$ colors? Settle this for every $d \ge 3$, or find a degree for which it is impossible for every finite $q$. The field need not be a finite-range function of independent vertex labels, nor generated by a bounded-round algorithm.

Source: Liggett and Tang (2023), introduction, who ask for an automorphism-invariant one-dependent coloring of the d-regular tree for each d ≥ 3; stated with invariance under permutations of the colors 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, regular trees

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},
}
@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{timar2026,
  author        = {Tim{\'a}r, {\'A}d{\'a}m},
  title         = {Finitely dependent random colorings of bounded degree graphs},
  journal       = {Ann. Inst. Henri Poincar{\'e} Probab. Stat.},
  volume        = {62},
  number        = {1},
  year          = {2026},
  pages         = {747--750},
  doi           = {10.1214/26-AIHP1653},
  eprint        = {2402.17068},
  archivePrefix = {arXiv},
}
@misc{aim-regular-tree-one-dependent-coloring,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Automorphism-invariant one-dependent colorings of regular trees}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/583-regular-tree-one-dependent-coloring.md},
  note         = {Entry 583 at commit a153f46, 2026-10-13},
}

Resolution claims

Symmetric one-dependent colorings of regular trees v1 GitHub ↗

Kaiwen Jin

For every integer $d\geq3$, we construct a proper coloring of the infinite $d$-regular tree with finitely many colors whose law is one-dependent and invariant under every tree automorphism and every permutation of the colors. The construction uses symmetric tensors in a real Hilbert space. Orthogonal projections force adjacent colors to differ, tensor summation gives consistent finite-dimensional laws, and a uniform …

Full resolution · not verified · fidelity not established · posted on GitHub 13 Oct 2026

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-00768, "Automorphism-invariant one-dependent colorings of regular trees", clopen.solutions.