Pattern avoiding permutations and Brownian excursion
Authors:
Preprint
Abstract
Permutations that avoid given patterns are some some the most classical objects in combinatorics with strong connections to many fields of mathematics, computer science and biology. In this paper we study the scaling limits of a random permutation avoiding a pattern of length 3 and their relations to Brownian excursion. Exploring this connection to Brownian excursion allows us to strengthen the recent results of Elizalde [13], Madras and Pehlivan [25] and Miner and Pak [29] as well as to understand many of the interesting phenomena that had previously gone unexplained.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Patterns in Random Permutations Avoiding the Pattern 132Combinatorics, Probability and Computing, 2016
- Structure of random 312‐avoiding permutationsRandom Structures & Algorithms, 2015
- The shape of random pattern-avoiding permutationsAdvances in Applied Mathematics, 2014
- A variant of the tandem duplication — random loss model of genome rearrangementTheoretical Computer Science, 2009
- Tableaux combinatorics for the asymmetric exclusion processAdvances in Applied Mathematics, 2007
- Bijections for refined restricted permutationsJournal of Combinatorial Theory, Series A, 2004
- On the distribution of the length of the longest increasing subsequence of random permutationsJournal of the American Mathematical Society, 1999
- Some Combinatorial Properties of Schubert PolynomialsJournal of Algebraic Combinatorics, 1993
- Conditional limit theorems for branching processesInternational Journal of Stochastic Analysis, 1991
- Sorting Using Networks of Queues and StacksJournal of the ACM, 1972