On the Length of the Longest Increasing Subsequence in a Random Permutation
Béla Bollobás, Svante Janson · Cambridge University Press eBooks · 1997
. Complementing the results claiming that the maximal length Ln of an increasing subsequence in a random permutation of f1; 2; : : : ; ng is highly concentrated, we show that Ln is not concentrated in a short interval: sup l P(l Ln l + n 1=16 log \\Gamma3=8 n) ! 0 as n !1. 1. Introduction Ulam [9] proposed the study of L n , the maximal length of an increasing subsequence of a random permutation of the set [n] = f1; 2; : : : ; ng. Hammersley [4], Logan and Shepp [7], and Versik and Kerov [10] proved that EL n ¸ 2 p n and L n = p n p \\Gamma! 2 as n !1: (1.1) Frieze [3] showed that the distribution of L n is sharply concentrated about its mean; his result was improved by Bollob'as and Brightwell [2], who in particular proved that Var(L n ) = O(n 1=2 \\Gamma log n= log log n) 2 \\Delta : (1.2) (The log factors have recently been removed by Talagrand [8].) Somewhat surprisingly, it is not known that the distribution of L n is not much more concentrated than claimed by (1.2...