### Abstract -- Jinho Baik

Longest increasing subsequences and random matrices

The asymptotics of the length, *L*_{N}, 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(i*_{1})< p(i_{2})< ... < p(i_{k}) with *1 <= i*_{1}< ... < i_{k} <= N. Then *L*_{N}(p) is defined to be the length of the *longest* increasing subsequence of *p*. Thus *L*_{N} is a random
variable on the probability space *S*_{N}, 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
*L*_{N}, 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:**
On the Ulam's problem : D.Aldous and P.Diaconis, *Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem*, Bull. Amer. Math. Soc., 36 (1999) 413-432.

On the connection to the random matrix theory : P.Deift,
*Integrable systems and combinatorial theory*, Notices Amer. Math. Soc., 47
(2000) 631-640.

Click here for pdf version.

Return to: DMJ-IMRN Conference * Math Department * Duke University

Last modified: March 7, 2001

webmaster@math.duke.edu