|COMPUTER/SCIENCE DISCRETE MATH, II|
|Topic:||Extremal Erodos-Szekeres Permutations and Square Young Tableaux|
|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.