A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three
type: Item
instance of: scholarly article
title: A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three
author: Jungeun Park
author: Douglas Rizzolo
published in: Electronic Communications in Probability
publication date: 2024-10-29T00:00:00Z
review text: 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.''
reviewed by: Andrius Grigutis
Mathematics Subject Classification ID: 60J80
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60F05
zbMATH DE Number: 7935191
zbMATH Keywords: Galton-Watson trees
zbMATH Keywords: local limits
zbMATH Keywords: pattern avoiding permutations
MaRDI profile type: Publication
cites work: Local limits of conditioned Galton-Watson trees: the infinite spine case
cites work: On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
cites work: Tree-valued Markov chains derived from Galton-Watson processes
cites work: Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
cites work: A decorated tree approach to random permutations in substitution-closed classes
cites work: Almost square permutations are typically square
cites work: Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
cites work: Square permutations are typically rectangular
cites work: Longest increasing subsequences in pattern-restricted permutations
cites work: Pattern‐avoiding permutations and Brownian excursion part I: Shapes and fluctuations
cites work: Pattern-avoiding permutations and Brownian excursion. II: Fixed points
cites work: Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
cites work: Patterns in random permutations avoiding some sets of multiple patterns
cites work: The Galton-Watson process conditioned on the total progeny
cites work: Subdiffusive behavior of random walk on a random cluster
cites work: Probability on trees and networks
cites work: Structure of random \(312\)-avoiding permutations
cites work: Longest monotone subsequences and rare regions of pattern-avoiding permutations
cites work: Asymptotic distribution of fixed points of pattern-avoiding involutions
cites work: Arbres et processus de Galton-Watson. (Trees and Galton-Watson processes)
cites work: The Infinite limit of random permutations avoiding patterns of length three
cites work: The infinite limit of separable permutations
cites work: Regenerative random permutations of integers
cites work: Permutations without long decreasing subsequences and random matrices
DOI: 10.1214/24-ECP613
description: scientific article; zbMATH DE number 7935191