abstract
COMPUTER/SCIENCE DISCRETE MATH, II | |
Topic: | Extremal Erodos-Szekeres Permutations and Square Young Tableaux |
Speaker: | Dan Romik |
Affiliation: | MSRI, Berkeley |
Date: | Tuesday, May 3 |
Time/Room: | 10:30am - 12:30pm/S-101 |
An Extremal Erdos-Szekeres permutation is a permutation of the numbers 1,2,...,N^2 that has no monotone subsequence of length N+1 (and is therefore extremal with respect to the Erdos-Szekeres theorem). If an EES permutation is drawn uniformly at random, the plot of its values clusters inside a limiting shape (see http://www.msri.org/people/members/dromik/mathpics/perm.jpg ). I will relate this to the limiting shape of the uniformly random square NxN Young tableau, found recently by me and Boris Pittel.