Zigzag diagrams and Martin boundary (Q1800814)

Martin boundary theory is a classical branch of probability concerned with characterizations of nonnegative harmonic measures and behaviours of transient random walks on a set $S$. A brief introduction can be found in [\textit{S. A. Sawyer}, Contemp. Math. 206, 17--44 (1997; Zbl 0891.60073)]. In practice, the theory boils down to the problem of characterizing extreme harmonic measures called the minimal boundary of $S$, which is a subset (sometimes strict subset) of the Martin boundary of $S$. Minimal boundaries and Martin boundaries have been characterized for various infinite graphs, such as $d$-regular trees and the Cayley graph of finite groups. This paper characterizes the minimal boundary for a particular infinite graph $\mathcal{Z}$ constructed as follows. Fix an alphabet $A$. The set of words on $A$ is the free monoid $A^\ast$. View it as graded graph, where grading is given by the length of the words, and $w \sim w'$ if $w$ is a subword of $w'$ and the length of $w'$ is one more than the length of $w$. This is the graph $\mathcal{Z}$. Compared to the aforementioned examples of infinite graphs, $\mathcal{Z}$ seems rather more complicated. \textit{G. Viennot} [J. Comb. Theory, Ser. A 34, 1--14 (1983; Zbl 0518.05006)] first introduced and studied this graph in 1983. For the two-letter alphabet $A = A_2 = \{+,-\}$, he noted that the number of maximal chains of length $n-1$, starting from the empty word, is equal to $n!$. Then he proved this by producing two interesting bijections between paths on $\mathcal{Z}$ and permutations of $[n]$ (Figure 2 of paper). This combinatorial link allows one to reinterpret random paths on $\mathcal{Z}$ in terms of random permutations. \textit{A. Gnedin} and \textit{G. Olshanski} [Int. Math. Res. Not. 2006, No. 4, Article ID 51968, 39 p. (2006; Zbl 1102.05001)] used this bijection to describe the set of Gibbs measures on this graph. These are the harmonic measures supported on the set of infinite paths in $\mathcal{Z}$. As harmonic measures supported on finite paths admit a simple characterization, the Gibbs measures are the interesting ones. This paper resolves the main missing links in the work of Gnedin and Olshanski [loc. cit.]. First, it gives a geometric meaning to the harmonic measures identified by Gnedin and Olshanski, and thereby showing that the minimal boundary is equal to the Martin boundary on $\mathcal{Z}$. Second, it uses combinatorial bijections between permutations and Young tableaux to provide a correspondence between paths on $\mathcal{Z}$ and paths on the Young graph $\mathcal{Y}$, which in turn has bijections to paths on the Kingman's partition graph $\mathcal{P}$ and the composition graph $\mathcal{C}$. Prior to this work, connections between $\mathcal{Z}$ and $\mathcal{Y}$ were only known at the level of harmonic measures. The key arguments are given in section 2 of the paper, accompanied with nice diagrams. The paper is clearly written and is particularly accessible to graduate students in probability.