Finitary coloring. (English) Zbl 1385.60048

The topic of the article is the coloring of \({\mathbb{Z}^d}\), \(d\geq 1\), by \({q\in\mathbb{N}}\) colors and the study of asymptotic properties of some existing \(q\)-coloring. More precisely, a \(q\)-coloring of \({\mathbb{Z}^d}\) is a random element \(X=(X_v)_{v\in\mathbb{Z}^d}\) of a probability space \({(\{1,\ldots,q\}^{\mathbb{Z}^d},\mathbb{P})}\) such that \({\mathbb{P}(X_u\neq X_v)=1}\) whenever \({|u-v|=1}.\) The authors assume that coloring is a finitary factor of an i.i.d. process (ffiid), i.e., \({X=F(Y)},\) where \(F\) is a measurable functions invariant under shifts of \(\mathbb{Z}^d\) and \({Y=(Y_v)_{v\in\mathbb{Z}^d}}\) are i.i.d. variables. Furthermore, for almost every \(y\) (under distribution of \(Y\)) there exists \({0\leq r<\infty}\) such that whenever \(\tilde{y}\) agrees with \(y\) on the ball \[ {B(r):=\{v\in\mathbb{Z}^d : |v|=|v_1|+\cdots+|v_d|\leq r\}}, \] the zero values agree: \({F(y)_0=F(\tilde(y))_0}\). In that case, \(R(y)\) is the minimum of \(r\) with such property and \(R(Y)\) is a coding radius.
The main results are statements on asymptotic distribution of the coding radius. Let \(\mathrm{tower}(r)=\underbrace{\exp\exp\ldots\exp}_{\lfloor r\rfloor\;\text{times}}1,\) then in the cases \(d=1\), \(q\geq3\) and \(d\geq2\), \(q\geq4\) there exist constants \(c,C>0\) such that:
for every ffiid \(q\)-coloring \({\mathbb{P}(R>r)>1/\mathrm{tower}(Cr)}\) for any \({r\geq 0};\)
there exists a ffiid \(q\)-coloring with \({\mathbb{P}(R>r)<1/\mathrm{tower}(cr)}\) for any \({r\geq0}\). In the cases \(d\geq2\) \(q=3\);
for every ffiid 3-coloring \({\mathbb{E}(R^2)=\infty}\);
there exists ffiid 3-coloring with \({\mathbb{P}(R>r)<r^{-\alpha}}\) for any \({r\geq0}\) and some \({\alpha=\alpha(d)>0}.\)
Also in the case \(d=1\), a generalization using shifts of finite type is presented.


60G10 Stationary stochastic processes
05C15 Coloring of graphs and hypergraphs
37A50 Dynamical systems and their relations with probability theory and stochastic processes
Full Text: DOI arXiv Euclid