Jump to content

Baik–Deift–Johansson theorem

From Wikipedia, the free encyclopedia

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

[edit]

For each let be a uniformly chosen permutation with length . Let be the length of the longest, increasing subsequence of .

Then we have for every that

where is the Tracy-Widom distribution of the Gaussian unitary ensemble.

Literature

[edit]
  • 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

[edit]
  1. ^ Baik, Jinho; Deift, Percy; Johansson, Kurt (1998). "On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations". arXiv:math/9810105.
  2. ^ Romik, Dan (2015). The Surprising Mathematics of Longest Increasing Subsequences. doi:10.1017/CBO9781139872003. ISBN 9781107075832.