Longest increasing subsequences, the Hammersley process and the Laguerre Unitary Ensemble
A talk in the Seminar Zufallsmatrizen series by
Anthony Mays from University of Melbourne
| Abstract: | A classical problem in probability and combinatorics is to uniformly at random choose a
permutation of (1,2, ...,_N_) and find the longest increasing subsequence. Related is the Hammersley process, which essentially takes the permutation length _N_ to be a Poisson distributed random variable with rate _z_^2, and again looks for the longest increasing subsequence. A remarkable result of Baik, Deift & Johansson tells us that the cumulative distribution function (CDF) of the centred and rescaled length in both the fixed _N_ and Hammersley processes is given by the distribution of the (centred and rescaled) largest eigenvalue of the Laguerre Unitary Ensemble (LUE), in the large _N_ or _z_ limit. Similarly, Borodin & Forrester show that for finite _z_ the Hammersley CDF is given by the distribution of the (centred and rescaled) smallest eigenvalue of the LUE. This allows us to use the "hard-to-soft edge transition" to explore the next order corrections to these CDFs, which expands on and refines results of Baik and Jenkins. We derive expressions for the Hammersley process in terms of Fredholm determinants and Painlevé transcendents, and provide numerical evidence for the corrections to the fixed-_N_ longest increasing subsequence problem. Please contact Gernot Akemann (akemann@physik.uni-bielefeld.de) for details. Within the CRC this talk is associated to the project(s): C6 |