Finitary coloring
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: {\parindent=0.7cm \begin{itemize}\item[(1)] for every ffiid \(q\)-coloring \({\mathbb{P}(R>r)>1/\mathrm{tower}(Cr)}\) for any~\({r\geq 0};\) \item[(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\); \item[(3)] for every ffiid 3-coloring \({\mathbb{E}(R^2)=\infty}\); \item[(4)] there exists ffiid 3-coloring with \({\mathbb{P}(R>r)<r^{-\alpha}}\) for any~\({r\geq0}\) and some \({\alpha=\alpha(d)>0}.\) \end{itemize}} Also in the case \(d=1\), a generalization using shifts of finite type is presented.
- Local mending
- Distributed algorithms for fractional coloring
- Finitary isomorphisms of renewal point processes and continuous-time regenerative processes
- Mallows permutations and finite dependence
- What can be sampled locally?
- One-dependent coloring by finitary factors
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Finitely dependent coloring
- scientific article; zbMATH DE number 5035591 (Why is no real title available?)
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- Uniform even subgraphs and graphical representations of Ising as factors of i.i.d.
- One-dependent colorings of the star graph
- Symmetrization for finitely dependent colouring
- Finitely dependent random colorings of bounded degree graphs
- Large-scale geometry of Borel graphs of polynomial growth
- Finitely dependent processes are finitary
- Finitary codings for spatial mixing Markov random fields
This page was built for publication: Finitary coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1681594)
