The Infinite Limit of Random Permutations Avoiding Patterns of Length Three

Abstract

For $\tau \in S_3$, let ${\mu }_n^{\tau }$ denote the uniformly random probability measure on the set of $\tau$-avoiding permutations in $S_n$. Let ${\mathbb{N}}^{\ast }=\mathbb{N}\cup \{\infty \}$ with an appropriate metric and denote by $S(\mathbb{N},{\mathbb{N}}^{\ast })$ the compact metric space consisting of functions $\sigma =\{{\sigma }_i{\}}_{i=1}^{\infty }$ from $\mathbb{N}$ to ${\mathbb{N}}^{\ast }$ which are injections when restricted to ${\sigma }^{-1}(\mathbb{N})$\rm; that is, if ${\sigma }_i={\sigma }_j$, $i\ne j$, then ${\sigma }_i=\infty$. Extending permutations $\sigma \in S_n$ by defining ${\sigma }_j=j$, for $j>n$, we have $S_n\subset S(\mathbb{N},{\mathbb{N}}^{\ast })$. For each $\tau \in S_3$, we study the limiting behavior of the measures $\{{\mu }_n^{\tau }{\}}_{n=1}^{\infty }$ on $S(\mathbb{N},{\mathbb{N}}^{\ast })$.

Some minor editorial changes were implemented