Extremal Erodos-Szekeres Permutations and Square Young Tableaux

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.