Algebraic aspects of increasing subsequences

Dr. Eric Rains

AT&T Labs--Research

October 18,



There has recently been an upsurge of activity related to the distribution of the length of the longest increasing subsequence of a random permutation, caused in large part by the recent discovery by Baik, Deift, and Johansson of an asymptotic connection between increasing subsequences and (complex Hermitian) Gaussian random matrices. Underlying their initial proof was an exact relation between the increasing subsequence problem and certain integrals over the unitary group. In this talk, I will describe this relation, as well as generalizations to multisets, involutions, etc., with particular attention to a new interpretation and proof in terms of invariant theory. In particular, for each of the unitary, orthogonal, and symplectic groups, one can describe the joint invariants of a collection of tensors in terms of increasing subsequences of multisets; in the case of the unitary group, this specializes to the classical straightening algorithm. Time permitting, I will also discuss some asymptotic consequences.

The papers upon which the talk is based can be found at:

Return to Applied Math Colloquium home page