Baik–Deift–Johansson theorem

The Baik–Deift–Johansson theorem is a result from probabilistic combinatorics. It deals with the subsequences of a randomly uniformly drawn permutation from the set $\{1,2,\dots ,N\}$. The theorem makes a statement about the distribution of the length of the longest increasing subsequence in the limit. The theorem was influential in probability theory since it connected the KPZ-universality with the theory of random matrices.

The theorem was proven in 1999 by Jinho Baik, Percy Deift and Kurt Johansson.

Statement

For each $N\ge 1$ let ${\pi }_N$ be a uniformly chosen permutation with length $N$. Let $l({\pi }_N)$ be the length of the longest, increasing subsequence of ${\pi }_N$.

Then we have for every $x\in ℝ$ that

$\mathbb{P}(\frac{l({\pi }_N)-2\sqrt{N}}{N^{1/6}}\le x)\to F_2(x),N\to \mathrm{\infty }$

where $F_2(x)$ is the Tracy-Widom distribution of the Gaussian unitary ensemble.

Literature

• Template:Cite book
• Template:Cite journal

References

Template:Combin-stub