The asymptotics of the length, LN, of the longest increasing subsequence of a random permutation was initially a combinatorial problem asked by Ulam around 1950. Given a random permutation p of N letters, an increasing subsequence of p is a sequence p(i1)< p(i2)< ... < p(ik) with 1 <= i1< ... < ik <= N. Then LN(p) is defined to be the length of the longest increasing subsequence of p. Thus LN is a random variable on the probability space SN, the symmetric group, with uniform probability. This problem has applications, for example, to a card game called patience sorting. The article [AD] is a good survey for history, applications and results of the Ulam's problem.
Rather unexpected is its connection to the random matrix theory. The theory of random matrices started by the physicist Wigner again around 1950 for a study of complex atoms like Uranium. The (limiting) statistics of eigenvalues of a class of random matrices have found a wide range of applications in physics and also mathematics. Among them are quantum chaos, quantum gravity and, surprisingly, the zeros of the Riemann-zeta function.
As proved by Baik, Deift and Johansson, the limiting fluctuation of LN, the longest increasing subsequence, is governed by the same distribution that describes the liming fluctuation of the largest eigenvalue of a random Hermitian matrix taken from the Gaussian unitary ensemble. In other words, if we take proper centering and scaling, for large N, the longest increasing subsequence of a random permutation behaves statistically like the largest eigenvalue of a random Hermitian matrix. These developments are surveyed in [Deift]. Soon after, this relation was extended to a handful of related questions like random words and random growth models by many authors.
The key point in these relations seems to be a universality, or central limit theorem. There are universality results for the largest eigenvalue distribution in the random matrix theory. However, in the random permutation context, the universality is yet to be proved. We discuss what the proper setting for the central limit theorem in the random permutation context should to be and what results we hope to obtain.Survey papers:
Return to: DMJ-IMRN Conference * Math Department * Duke University