Context-free pairs of groups. II: Cuts, tree sets, and random walks (Q658032)

\textit{T. Ceccherini-Silberstein} and the author of this article considered in [Eur. J. Comb. 33, No. 7, 1449--1466 (2012; Zbl 1279.68140)] pairs \((G,K)\) consisting of a finitely generated group and a subgroup, such that the Schreier graph \(\mathfrak X\) (with cosets \(gK\) as vertices and edges given by multiplication by \(G\)s generating set \(S\)). Cones are connected components of complements of balls in \(\mathfrak X\) centered at \(1\cdot K\), and \(\mathfrak X\) is said to be context-free if it has finitely many isomorphism types of cones. The authors prove that \(\mathfrak X\) is context-free if and only if the set of words over \(S\) that evaluate to elements of \(K\) is a context-free language. This extends the seminal work by \textit{D. E. Muller} and \textit{P. E. Schupp} [J. Comput. Syst. Sci. 26, 295--310 (1983; Zbl 0537.20011)]. The present paper introduces a generalization of the definition of cones of context-free graphs; namely, an axiomatization by ``tree sets'' in \(\mathfrak X\), i.e.\ collections of infinite subgraphs with infinite complement, which are either nested or disjoint, with uniformly bounded finite boundary. The axioms guarantee that the Hasse diagram of the poset of cuts is a tree. Note that the set of cones is a tree set, but there may exist ``more efficient'' tree sets, in the sense that they have fewer isomorphism classes. A tree set has finite type if its members cover \(\mathfrak X\) and are themselves covered by their sub-members, up to finitely many vertices. The author proves that \(\mathfrak X\) admits a finite-type tree set if and only if, for some (or, equivalently, all) vertices \(x\in\mathfrak X\) the language \(L_{x,x}=\{w\in S^*\mid wx=x\}\) is context-free. The author then applies his considerations to random walks on context-free graphs. He proves that, if \(\mathfrak X\) has a finite-type tree set, then the growth \(\#(L_{x,x}\cap S^n)\) of these languages is of the form \(c_x\lambda^n\) or \(c_x\lambda^nn^{-1/2}\) or \((c_x+(-1)^n\overline c_x)\lambda^nn^{-3/2}\), extending results by \textit{S. P. Lalley} [Ann. Probab. 21, No. 4, 2087--2130 (1993; Zbl 0804.60006); Contemp. Math. 287, 201--230 (2001; Zbl 1016.60050)] on random walks on free groups.