A decorated tree approach to random permutations in substitution-closed classes (Q782811)

This paper analyzes random permutations from substitution-closed classes via a probabilistic approach. Given a substitution-closed class \(C\) with the set \(S\) of simple permutations for \(i\) in \([n]\), the generating function of \(S\) is also denoted by \(S\) for convenience. Its radius of convergence is denoted by \(\rho_S\). For a permutation \(v\) and a pattern \(\pi\), denote by \(c\)-\(occ(\pi,v)\) the number of consecutive occurrences of pattern \(\pi\) in \(v\). Suppose that \(S'(\rho_S)\ge1/(1+\rho_S)^2-1\). Consider a uniform random permutation \(v_n\) of size \(n\) in \(C\), where \(n\) is any positive integer. By identifying the packed forest associated with a uniform random permutation in a substitution-closed class as a conditioned mono-type Galton-Waston forest, it is shown that for each pattern \(\pi\in C\), there exists \(\gamma\in[0,1]\) such that \(\frac1n c\)-\(occ(\pi,v_n)\rightarrow\gamma\) in probability as \(n\) tends to infinity.