Hydrodynamical methods for analyzing longest increasing subsequences

摘要

Let Ln be the length of the longest increasing subsequence of a random permutation of the numbers 1,…,n, for the uniform distribution on the set of permutations. We discuss the “hydrodynamical approach” to the analysis of the limit behavior, which probably started with Hammersley (Proceedings of the 6th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1 (1972) 345–394) and was subsequently further developed by several authors. We also give two proofs of an exact (non-asymptotic) result, announced in Rains (preprint, 2000).