UW Combinatorics SeminarThe shape of random pattern avoiding perutationsIgor PakUCLA
September 25, 4:00pm 
ABSTRACT


There are dozens of different "Catalan structures", which are combinatorial objects counted with Catalan numbers. Many of these are connected by various bijections, but some are clearly different from others. One approach to understand the nature of these differences is to look at the likely shape of random large combinatorial objects. Some of these have been classically studied in probability to obtain often delicate results We investigate two classes of permutations without forbidden 3patterns, 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. Somewhat mysteriously, there are several phasetransition regions whose nature is yet to be explained. At the end, I will explain how some of our results are closely related to known properties of a Brownian excursion, and state some open problems. Joint work with Sam Miner. 
Sara Billey, Combinatorics Seminar, Mathematics Department, University of Washington, 

