tailieunhanh - Báo cáo toán học: " INCREASING SUBSEQUENCES AND THE CLASSICAL GROUPS"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: INCREASING SUBSEQUENCES AND THE CLASSICAL GROUPS. | INCREASING SUBSEQUENCES AND THE CLASSICAL GROUPS E. M. Rains AT T Research Submitted November 24 1997 Accepted January 30 1998 Abstract. We show that the moments of the trace of a random unitary matrix have combinatorial interpretations in terms of longest increasing subsequences of permutations. To be precise we show that the 2n-th moment of the trace of a random k-dimensional unitary matrix is equal to the number of permutations of length n with no increasing subsequence of length greater than k. We then generalize this to other expectations over the unitary group as well as expectations over the orthogonal and symplectic groups. In each case the expectations count ob jects with restricted increasing subsequence length. Introduction Much work has been done in the combinatorial literature on the increasing subsequence problem that of studying the distribution of the length of the longest increasing subsequence of a random permutation. The problem was first considered by Hammersley 5 good summaries can be found in 1 and 10 which gives an alternate proof of Theorem . This problem is also closely connected to the representation theory of Sn particularly the theory of Young tableaux. The representation theory aspects are covered in 13 section in 8 gives a good treatment of the more elementary Young tableaux results. The results reported here arose from the observation that a certain partial sum of characters of the symmetric group that occurs naturally in the increasing subsequence problem also appears when calculating certain expectations over the unitary group. In particular it turns out that the distribution of the length of the longest increasing subsequence can be expressed exactly in terms of the moments of the trace of a random uniformly distributed unitary matrix. This correspondence generalizes both to other moments for the unitary group and to the moments of the trace of a random orthogonal or symplectic matrix. In each case the moments count .