The shape of random pattern-avoiding permutations

09/23/2014 - 12:15pm
09/23/2014 - 1:10pm
Sam Miner (UCLA)

There are dozens of different "Catalan structures", which are combinatorial objects enumerated by the Catalan numbers. Many of these have been classically studied in probability to obtain often delicate results on the "shape" of these random structures. We investigate two classes of permutations without forbidden 3-patterns, which were introduced by Knuth in his studies of sorting. These are known Catalan structures which have been extensively generalized and studied in the past two decades. We prove some rather detailed results about the shapes of random permutations in these two classes. All the proofs come from bijective and asymptotic combinatorics - we will sketch the reasoning behind these proofs, and also mention potential generalizations to permutations with forbidden sets of k-patterns. Joint work with Igor Pak.

Mudd Science Library 126, Pomona College