UW Combinatorics Talk

UW Combinatorics Seminar

The shape of random pattern avoiding perutations

Igor Pak

UCLA

September 25, 4:00pm
Padelford C-401

refreshments at 3:30pm
Pre-Seminar at 2:30pm in Padelford C-401

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 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. Somewhat mysteriously, there are several phase-transition 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.


Speaker's Contact Info: http://www.math.ucla.edu/~pak/


Return to seminar home page

Sara Billey, Combinatorics Seminar, Mathematics Department, University of Washington,

Page loaded on September 23, 2013 at 04:44 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.