## Percolation of arbitrary words in $$\{0, 1\}^ \mathbb{N}$$.(English)Zbl 0832.60095

Summary: Let $${\mathcal G}$$ be a (possibly directed) locally finite graph with countably infinite vertex set $${\mathcal V}$$. Let $$\{X(v) : v \in {\mathcal V}\}$$ be an i.i.d. family of random variables with $P\{X(v) = 1\} = 1 - P \{X(v) = 0\} =p.$ Finally, let $$\xi = (\xi_1, \xi_2, \ldots)$$ be a generic element of $$\{0,1\}^\mathbb{N}$$; such a $$\xi$$ is called a word. We say that the word $$\xi$$ is seen from a vertex $$v$$ if there exists a self- avoiding path $$(v, v_1, v_2, \ldots)$$ on $${\mathcal G}$$ starting at $$v$$ and such that $$X(v_i) = \xi_i$$ for $$i \geq 1$$. The traditional problem in (site) percolation is whether $$P \{(1,1,1, \dots)$$ is seen from $$v\} > 0$$. So-called $$AB$$-percolation occurs if $$P\{ (1,0,1,0,1,0, \dots)$$ is seen from $$v\} > 0$$. Here we investigate (a) whether $$P$${all words are seen from $$v\} > 0$$ (for a fixed $$v)$$ and (b) whether $$P$${all words are seen from some $$v\} = 1$$. We show that both answers are positive if $${\mathcal G} = \mathbb{Z}^d$$, or even $$\mathbb{Z}^d_+$$ with all edges oriented in the “positive direction”, when $$d$$ is sufficiently large. We show that on the oriented $$\mathbb{Z}^3_+$$ the answer to (a) is negative, but we do not know the answer to (b) on $$\mathbb{Z}^3_+$$. Various graphs $${\mathcal G}$$ are constructed (almost all of them trees) for which the set of words $$\xi$$ which can be seen from a given $$v$$ (or from some $$v)$$ is large, even though it is w.p. 1 not the set of all words.

### MSC:

 60K35 Interacting random processes; statistical mechanics type models; percolation theory 82B43 Percolation

### Keywords:

percolation; oriented percolation; words; graphs; trees
Full Text: