Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-07T00:57:25.852Z Has data issue: false hasContentIssue false

The Infinite limit of random permutations avoiding patterns of length three

Published online by Cambridge University Press:  14 October 2019

Ross G. Pinsky*
Affiliation:
Department of Mathematics, Technion–Israel Institute of Technology, Haifa, 32000, Israel Email: pinsky@math.technion.ac.il, http://www.math.technion.ac.il/~pinsky/
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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}^*} = {\mathbb {N}} \cup \{ \infty \} $$ with an appropriate metric and denote by $$S({\mathbb{N}},{\mathbb{N}^*})$$ the compact metric space consisting of functions $$\sigma {\rm{ = }}\{ {\sigma _i}\} _{i = 1}^\infty {\rm{ }}$$ from $$\mathbb {N}$$ to $${\mathbb {N}^ * }$$ which are injections when restricted to $${\sigma ^{ - 1}}(\mathbb {N})$$; that is, if $${\sigma _i}{\rm{ = }}{\sigma _j}$$, $$i \ne j$$, then $${\sigma _i} = \infty $$. Extending permutations $$\sigma \in {S_n}$$ by defining $${\sigma _j} = j$$, for $$j \gt n$$, we have $${S_n} \subset S({\mathbb{N}},{{\mathbb{N}}^*})$$. For each $$\tau \in {S_3}$$, we study the limiting behaviour of the measures $$\{ \mu _n^\tau \} _{n = 1}^\infty $$ on $$S({\mathbb{N}},{\mathbb{N}^*})$$. We obtain partial results for the permutation $$\tau = 321$$ and complete results for the other five permutations $$\tau \in {S_3}$$.

Type
Paper
Copyright
© Cambridge University Press 2019 

References

Bassino, F., Bouvel, M., Féray, V., Gerin, L. and Pierrot, A. (2018) The Brownian limit of separable permutations. Ann. Probab. 46 21342189.CrossRefGoogle Scholar
Bona, M. (2004) Combinatorics of Permutations, Chapman & Hall/CRC.CrossRefGoogle Scholar
Gnedenko, B. V. and Kolmogorov, A. N. (1968) Limit Distributions for Sums of Independent Random Variables, revised edition, Addison-Wesley.Google Scholar
Gnedin, A. and Olshanski, G. (2010) q-exchangeability via quasi-invariance. Ann. Probab. 38 21032135.CrossRefGoogle Scholar
Gnedin, A. and Olshanski, G. (2012) The two-sided infinite extension of the Mallows model for random permutations. Adv. Appl. Math. 48 615639.CrossRefGoogle Scholar
Hoffman, C., Rizzolo, D. and Slivken, E. (2017) Pattern-avoiding permutations and Brownian excursion, I: Shapes and fluctuations. Random Structures Algorithms 50 394419.CrossRefGoogle Scholar
Janson, S. (2017) Patterns in random permutations avoiding the pattern 132. Combin. Probab. Comput. 26 2451.CrossRefGoogle Scholar
Miner, S. and Pak, I. (2014) The shape of random pattern-avoiding permutations. Adv. Appl. Math. 55 86130.CrossRefGoogle Scholar
Pinsky, R. G. (2014) Problems from the Discrete to the Continuous: Probability, Number Theory, Graph Theory, and Combinatorics, Universitext, Springer.CrossRefGoogle Scholar
Pitman, J. and Tang, W. (2019) Regenerative random permutations of integers. Ann. Probab. 47 13781416.CrossRefGoogle Scholar