Baik–Deift–Johansson theorem

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

Then we have for every ${\displaystyle x\in \mathbb {R} }$ that

${\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 ${\displaystyle F_{2}(x)}$ is the Tracy-Widom distribution of the Gaussian unitary ensemble.

• 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.