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 } {\displaystyle \{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 ≥ 1 {\displaystyle N\geq 1} let π N {\displaystyle \pi _{N}} be a uniformly chosen permutation with length N {\displaystyle N} . Let l ( π N ) {\displaystyle l(\pi _{N})} be the length of the longest, increasing subsequence of π N {\displaystyle \pi _{N}} . Then we have for every x ∈ R {\displaystyle x\in \mathbb {R} } that
P ( l ( π N ) − 2 N N 1 / 6 ≤ x ) → F 2 ( x ) , N → ∞ {\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 }
where F 2 ( x ) {\displaystyle F_{2}(x)} 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.
References