zbMATH — the first resource for mathematics

One-dependent coloring by finitary factors. (English. French summary) Zbl 1370.60061
Summary: The author and T. M. Liggett [Forum Math. Pi 4, Article ID e9, 43 p. (2016; Zbl 1361.60025)] recently proved the existence of a stationary \(1\)-dependent \(4\)-coloring of the integers, the first stationary \(k\)-dependent \(q\)-coloring for any \(k\) and \(q\), and arguably the first natural finitely dependent process that is not a block factor of an i.i.d. process. That proof specifies a consistent family of finite-dimensional distributions, but does not yield a probabilistic construction on the whole integer line. Here we prove that the process can be expressed as a finitary factor of an i.i.d. process. The factor is described explicitly, and its coding radius obeys power-law tail bounds.

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