Finitary coloring. (English) Zbl 1385.60048

Holroyd, Alexander E.; Schramm, Oded; Wilson, David B.

Ann. Probab. 45, No. 5, 2867-2898 (2017).

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.

Reviewer: Ivan Podvigin (Novosibirsk)

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