Baik–Deift–Johansson theorem explained

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 , ... ,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.^{[1] [2]}

Statement

For each

N \geq 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 R thatP \left( (l(\pi _{N)-2\sqrt{N})/() }\leq x \right)\to F_2(x),\quad N \to \inftywhere F _{2(x)} is the Tracy-Widom distribution of the Gaussian unitary ensemble.

Literature

• Book: 10.1017/CBO9781139872003. The Surprising Mathematics of Longest Increasing Subsequences . 2015 . Romik . Dan . 9781107075832 .
• 10.1090/bull/1623. Commentary on "Longest increasing subsequences: From patience sorting to the Baik–Deift–Johansson theorem" by David Aldous and Persi Diaconis . 2018 . Corwin . Ivan . Bulletin of the American Mathematical Society . 55 . 3 . 363–374 . free .

References

1. Jinho. Baik. Percy. Deift. Kurt. Johansson. On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations . 1998 . math/9810105.
2. Book: 10.1017/CBO9781139872003 . The Surprising Mathematics of Longest Increasing Subsequences . 2015 . Romik . Dan . 9781107075832 .