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 [math]\displaystyle{ \{1,2,\dots,N\} }[/math]. 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 [math]\displaystyle{ N \geq 1 }[/math] let [math]\displaystyle{ \pi_N }[/math] be a uniformly chosen permutation with length [math]\displaystyle{ N }[/math]. Let [math]\displaystyle{ l(\pi_N) }[/math] be the length of the longest, increasing subsequence of [math]\displaystyle{ \pi_N }[/math].

Then we have for every [math]\displaystyle{ x \in \mathbb{R} }[/math] that

[math]\displaystyle{ \mathbb{P}\left(\frac{l(\pi_N)-2\sqrt{N}}{N^{1/6}}\leq x \right)\to F_2(x),\quad N \to \infty }[/math]

where [math]\displaystyle{ F_2(x) }[/math] is the Tracy-Widom distribution of the Gaussian unitary ensemble.

Literature

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