<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 1" %>
GL(n, q) and Increasing Subsequences in Non-Uniform Random Permutations
Jason Fulman
Mathematics Department, University of Pittsburgh, 301 Thackeray Hall, Pittsburgh, PA 15260, USA
Annals of Combinatorics 6 (1) p.19-32 March, 2002
AMS Subject Classification: 15A52, 05E05
Connections between longest increasing subsequences in random permutations and eigenvalues of random matrices with complex entries have been intensely studied. This note applies properties of random elements of the finite general linear group to obtain results about the longest increasing and decreasing subsequences in non-uniform random permutations.
Keywords: random matrix, increasing subsequence, random permutation, random partition.


1. D. Aldous and P. Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. (N.S.) 36 (1999) 413每432.

2. J. Baik, Riemann-Hilbert problems for last passage percolation, http://xxx.lanl.gov/ abs/math.PR/0107079.

3. J. Baik, P. Deift, and K. Johansson, On the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12 (1999) 1119每1178.

4. J. Baik and E. Rains, The asymptotics of monotone subsequences of involutions, Duke Math. J. 109 (2001) 205每281.

5. A. Borodin, A. Okounkov, and G. Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000) 481每515.

6. P. Deift, Integrable systems and combinatorial theory, Notices Amer. Math. Soc. 47 (2000) 631每640.

7. J. Fulman, Probability in the classical groups over finite fields: symmetric functions, stochastic algorithms and cycle indices, Ph.D. Thesis, Harvard University, 1997.

8. J. Fulman, A probabilistic approach to conjugacy classes in the finite general linear and unitary groups, J. Algebra 212 (1999) 557每590.

9. J. Fulman, Random matrix theory over finite fields, Bull. Amer. Math. Soc. (N.S.) 39 (2002) 51每85.

10. J. Fulman, A probabilistic proof of the Rogers-Ramanujan identities, Bull. London Math. Soc. 33 (2001) 397每407.

11. I. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990) 257每285.

12. I.N. Herstein, Topics in Algebra, 2nd Ed., Xerox Corporation, 1975.

13. K. Johansson, The longest increasing subsequence in a random permutation and a unitary random matrix model, Math. Res. Lett. 5 (1998) 63每82.

14. K. Johansson, Random growth and random matrices, Proceedings of the Third European Congress of Mathematics, to appear.

15. P.M. Neumann and C.E. Praeger, Cyclic matrices over finite fields, J. London Math. Soc. 52 (2) (1995) 263每284.

16. A. Okounkov, Infinite wedge and random partitions, Selecta Math. (N.S.) 7 (2001) 57每81.

17. R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, UK, 1999.

18. C. Tracy and H. Widom, On the distributions of the lengths of the longest monotone subsequences in random words, Probab. Theory Related Fields 119 (2001) 350每380.