zbMATH — the first resource for mathematics

Symmetric 1-dependent colorings of the integers. (English) Zbl 1385.60014
Summary: In a recent paper, we constructed a stationary 1-dependent 4-coloring of the integers that is invariant under permutations of the colors. This was the first stationary \(k\)-dependent \(q\)-coloring for any \(k\) and \(q\). When the analogous construction is carried out for \(q>4\) colors, the resulting process is not \(k\)-dependent for any \(k\). We construct here a process that is symmetric in the colors and \(1\)-dependent for every \(q\geq 4\). The construction uses a recursion involving Chebyshev polynomials evaluated at \(\sqrt{q}/2\).

60C05 Combinatorial probability
60G10 Stationary stochastic processes
05C15 Coloring of graphs and hypergraphs
Full Text: DOI arXiv