On Increasing Subsequences of Minimal ErdSs-Szekeres Permutations  

作　　者：Zhong Gen SU 

机构地区：[1]Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China

出　　处：《Acta Mathematica Sinica,English Series》2011年第8期1573-1580,共8页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China （Grant No. 10671176） and Natural Science Foun- dation of Zhejiang Province （Grant No. J20091364）

摘　　要：Let π be a minimal ErdSs-Szekeres permutation of 1, 2,..., n^2, and let ln,k be the length of the longest increasing subsequence in the segment （πr（1）,...,π（k））. Under uniform measure we establish an exponentially decaying bound of the upper tail probability for ln,k, and as a consequence we obtain a complete convergence, which is an improvement of Romik＇s recent result. We also give a precise lower exponential tail for ln,k.Let π be a minimal ErdSs-Szekeres permutation of 1, 2,..., n^2, and let ln,k be the length of the longest increasing subsequence in the segment （πr（1）,...,π（k））. Under uniform measure we establish an exponentially decaying bound of the upper tail probability for ln,k, and as a consequence we obtain a complete convergence, which is an improvement of Romik＇s recent result. We also give a precise lower exponential tail for ln,k.

关 键 词：Large deviation minimal Erd6s-Szekeres permutation Robinson-Schensted-Knuth cor- respondence Young tableaux 

分 类 号：O211.5[理学—概率论与数理统计] O157[理学—数学]