On increasing subsequences of random permutations

被引:23
作者
Kim, JH
机构
关键词
D O I
10.1006/jcta.1996.0095
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:148 / 155
页数:8
相关论文
共 12 条
[1]  
ALDOUS D, HAMMERSLEYS INTERACT
[2]  
BOLLOB\AS B., 1992, ANN APPL PROBAB, V2, P1009
[3]   THE LONGEST CHAIN AMONG RANDOM POINTS IN EUCLIDEAN-SPACE [J].
BOLLOBAS, B ;
WINKLER, P .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1988, 103 (02) :347-353
[4]  
BOLLOBAS B, P 1993 CAMBR ERD BIR
[5]  
DEUSCHEL J, LTD CURVES IID RECOR
[6]  
DEUSCHEL J, COMMUNICATION
[7]  
FRIEZE A., 1991, ANN APPL PROBAB, V1, P301
[8]  
KEROV S, 1977, DOKL AKAD NAUK SSSR, V233, P1024
[9]   VARIATIONAL PROBLEM FOR RANDOM YOUNG TABLEAUX [J].
LOGAN, BF ;
SHEPP, LA .
ADVANCES IN MATHEMATICS, 1977, 26 (02) :206-222
[10]   DESCENDING SUBSEQUENCES OF RANDOM PERMUTATIONS [J].
PILPEL, S .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1990, 53 (01) :96-116