A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three
Let \(\pi\) and \(\sigma\) be permatations of \(\{1,\,\ldots,\,n\}\) and \(\{1,\,\ldots,\,m\}\) repectively, where \(n>m\). The permutation \(\pi\) is said to contain the permumation \(\sigma\) if there exist indices \(i_1<\ldots<i_m\) such that for all \(j<k\), \(\pi(i_j)<\pi(i_k)\) iff \(\sigma(j)<\sigma(k)\) and the permutation \(\pi\) is said to avoid \(\sigma\) if it does not contain \(\sigma\).\N\NThe main result extends the work by \textit{R. G. Pinsky} [Comb. Probab. Comput. 29, No. 1, 137--152 (2020; Zbl 1434.60052)], where, according to the text, ``local limits are obtained for \(\sigma\neq 321\), but only partial results were obtained for \(\sigma=321\) and the question of whether or not the local limit existed was left open.''\N\NThe authors state that ``In the present paper we answer this question and show that the local limit does, in fact, exist. Our methods give a unified approach that works when \(\sigma\) is any pattern of length three.''\N\NThe main method is described as follows ``We rely on bijections with rooted ordered trees and we obtain local limits and descriptions of the limiting objects using deterministic arguments based on the local convergence of Galton-Watson trees conditioned on their number of vertices to size-biased Galton-Watson trees.''
scientific article; zbMATH DE number 7935191
scientific article