Combinatorial prequel to the Baik-Deift-Johansson theoremAlgebra & Discrete Mathematics
|Jonathan Novak, MSRI/University of Waterloo
|Fri, Nov 5 2010, 2:10PM
In 1999, Baik, Deift, and Johansson established a surprising link between asymptotic combinatorics and random matrix theory. Their result roughly says that the length of a longest increasing subsequence in a large random permutation and the top eigenvalue of a large random Hermitian matrix are equal in distribution. There were earlier signs of a link between these subjects - for instance Regev's 1981 observation that Mehta-Dyson type integrals are related to the asymptotics of the number of permutations with bounded increasing subsequence length, and Gessel's 1990 derivation of a Toeplitz determinant which acts as a generating function for such permutations. We will discuss the results of Gessel and Regev, and give combinatorial proofs of them based on notions such as rectangular complement of a Young diagram, the reflection principle for lattice walks in a Weyl chamber, and commutative raising and lowering operators on graded graphs.