## 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:
(1)
for every ffiid $$q$$-coloring $${\mathbb{P}(R>r)>1/\mathrm{tower}(Cr)}$$ for any $${r\geq 0};$$
(2)
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$$;
(3)
for every ffiid 3-coloring $${\mathbb{E}(R^2)=\infty}$$;
(4)
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.

### MSC:

 60G10 Stationary stochastic processes 05C15 Coloring of graphs and hypergraphs 37A50 Dynamical systems and their relations with probability theory and stochastic processes

### Keywords:

coloring; finitary factor; tower function; shift of finite type
Full Text: