The Shape of Random Pattern-Avoiding Permutations

2013/03/29 by Sam Miner, Miner, Sam, Igor Pak +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.1303.7313

38 pages, 14 figures. Fixed typos, added references and acknowledgments

arxiv created 2013/11/28 · arxiv updated 2013/12/02

Abstract

We initiate the study of limit shapes for random permutations avoiding a given pattern. Specifically, for patterns of length 3, we obtain delicate results on the asymptotics of distributions of positions of numbers in the permutations. We view the permutations as 0-1 matrices to describe the resulting asymptotics geometrically. We then apply our results to obtain a number of results on distributions of permutation statistics.

Related

• Patterns in random permutations avoiding some sets of multiple patterns
• Patterns in random permutations avoiding the pattern 321
• Distributions of several infinite families of mesh patterns
• Permutations avoiding a pattern of length three under Mallows distributions
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation