Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Permutations without long decreasing subsequences and random matrices. | Permutations without long decreasing subsequences and random matrices Piotr Sniady Institute of Mathematics University of Wroclaw pl. Grunwaldzki 2 4 50-384 Wroclaw Poland Submitted Jan 8 2006 Accepted Dec 31 2006 Published Jan 10 2007 Mathematics Subject Classifications 05E10 15A52 60J65 Abstract We study the shape of the Young diagram A associated via the Robinson-Schensted-Knuth algorithm to a random permutation in Sn such that the length of the longest decreasing subsequence is not bigger than a fixed number d in other words we study the restriction of the Plancherel measure to Young diagrams with at most d rows. We prove that in the limit n 1 the rows of A behave like the eigenvalues of a certain random matrix namely the traceless Gaussian Unitary Ensemble random matrix with d rows and columns. In particular the length of the longest increasing subsequence of such a random permutation behaves asymptotically like the largest eigenvalue of the corresponding random matrix. 1 Introduction Formulation of the problem Let an integer d 1 be fixed. For any integer n 1 we consider the set of the permutations X 2 Sn such that the length of the longest decreasing subsequence of X is not bigger than d in other words it is the set of the permutations avoiding the pattern d 1 d . 3 2 1 . Let Xn be a random element of this set probabilities of all elements are equal . In this article we are interested in the following problem Problem 1. Let Xn 2 Sn be a random permutation with the longest decreasing subsequence of length at most d. What can we say about the asymptotic behavior of the length of the longest increasing subsequence of Xn in the limit n 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R11 1 Let Xn Xn 1 . Xn d be the random Young diagram associated via the Robinson-Schensted-Knuth algorithm to Kn notice that since the number of the rows of Xn is equal to the length of the longest decreasing subsequence of n Xn has at most d rows .
