On increasing subsequences of random permutations

Let L(n) be the length of a longest increasing subsequence in a random permutation of {1,..., n}. It is known that the expected value of L(n) is asymptotically equal to 2 root n as n gets large. This note derives upper bound on the probability that L(n) - 2 root n exceeds certain quantities. In particular, we prove that L(n) - 2 root n is at most order n(1/6) with high probability. Our main result is an isoperimetric upper bound of the probability that L(n) - 2 root n exceed theta n(1/6), which suggests that the variance V[L(n)] might be n(1/3). We also find an explicit lower bound of the function beta(c) := -lim(n-->infinity)1/root n) log Pr(L(n) - 2 root n > c root n), c > 0, defined by D. Aldous and P. Diaconis. (C) 1996 Academic Press, Inc.