JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 16, No 2 (2002)

Jason Fulman

Using symmetric function theory, we study the cycle structure and increasing subsequence structure of permutations after iterations of various shuffling methods. We emphasize the role of Cauchy type identities and variations of the Robinson-Schensted-Knuth correspondence.

1. D. Aldous and P. Diaconis, “Shuffling cards and stopping times,” Amer. Math. Monthly 93 (1986), 333-348.
2. R. Arratia, A. Barbour, and S. Tavare, “On random polynomials over finite fields,” Math. Proc. Camb. Phil. Soc. 114 (1993), 347-368.
3. J. Baik, P. Deift, and K. Johansson, “On the distribution of the length of the longest increasing subsequence of random permutations,” J. Amer. Math. Soc. 12 (1999), 1119-1178.
4. J. Baik and E. Rains, “Algebraic aspects of increasing subsequences,” Preprint math.CO/9905083 at xxx.lanl.gov.
5. D. Bayer and P. Diaconis, “Trailing the dovetail shuffle to its lair,” Ann. Appl. Probab. 2 (1992), 294-313.
6. A. Berele and J. Remmel, “Hook flag characters and their combinatorics,” J. Pure Appl. Algebra 35 (1985), 225-245.
7. F. Bergeron and N. Bergeron, “Orthogonal idempotents in the descent algebra of Bn and applications,” J. Pure Appl. Algebra 79 (1992), 109-129.
8. N. Bergeron and L. Wolfgang, “The decomposition of Hochschild cohomology and the Gerstenhaber operations,” J. Pure Appl. Algebra 104 (1995), 243-265.
9. P. Bidigare, P. Hanlon, and D. Rockmore, “A combinatorial generalization of the spectrum of the Tsetlin library and its generalization to hyperplane arrangements,” Duke Math J. 99 (1999), 135-174.
10. P. Diaconis, “Group representations in probability and statistics,” Institute of Mathematical Statistics Lecture Notes (1988), Volume 11.
11. P. Diaconis, “From shuffling cards to walking around the building: An introduction to modern Markov chain theory,” in Proceedings of the International Congress of Mathematicians, Vol. 1, Berlin, 1998, Doc. Math. 1998, Extra Vol. I, 187-204 (electronic).
12. P. Diaconis, J. Fill, and J. Pitman, “Analysis of top to random shuffles,” Combin. Probab. Comput. 1 (1992), 135-155.
13. P. Diaconis, M. McGrath, and J. Pitman, “Riffle shuffles, cycles, and descents,” Combinatorica 15 (1995), 11-20.
14. A. Erdei, “Proof of a conjecture of Schoenburg on the generating function of a totally positive sequence,” Canad. J. Math 5 (1953), 86-94.
15. J. Fulman, “The combinatorics of biased riffle shuffles,” Combinatorica 18 (1998), 173-184.
16. J. Fulman, “Semisimple orbits of Lie algebras and card shuffling measures on Coxeter groups,” J. Algebra 224 (2000), 151-165.
17. J. Fulman, “Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting,” J. Algebra 231 (2000), 614-639.
18. J. Fulman, “Applications of the Brauer complex: Card shuffling, permutation statistics, and dynamical systems,” J. Algebra 243 (2001), 96-122.
19. J. Fulman, “Descent algebras, hyperplane arrangements, and shuffling cards,” Proc. Amer. Math. Soc. 129 (2001), 965-973.
20. T. Gannon, “The cyclic structure of unimodal permutations,” Discrete Math. 237 (2001), 149-161.
21. A. Garsia, “Combinatorics of the free Lie algebra and the symmetric group,” in “Analysis, et cetera,” Academic Press, Boston, 1990, pp. 309-382.
22. I. Gessel and C. Reutenauer, “Counting permutations with given cycle structure and descent set,” J. Combin. Theory Ser. A 64 (1993), 189-215.
23. P. Hanlon, “The action of Sn on the components of the Hodge decomposition of Hochschild homology,” Michigan Math. J. 37 (1990), 105-124.
24. J. Hansen, “Order statistics for decomposable combinatorial structures,” Rand. Struct. Alg. 5 (1994), 517-533.
25. K. Johansson, “Discrete orthogonal polynomial ensembles and the Plancharel measure,” Ann. of Math. (2) 153 (2001), 259-296.
26. S. Kerov and A. Vershik, “The characters of the infinite symmetric group and probability properties of the Robinson-Schensted-Knuth algorithm,” SIAM J. Algebraic Discrete Methods 7 (1986), 116-124.
27. G. Kuperberg, “Random words, quantum statistics, central limits, random matrices,” Preprint math.PR/9909104 at xxx.lanl.gov.
28. S. Lalley, “Cycle structure of riffle shuffles,” Ann. Probab. 24 (1996), 49-73. FULMAN
29. S. Lalley, “Riffle shuffles and their associated dynamical systems,” J. Theoret. Probab. 12 (1999), 903-932.
30. I. Macdonald, Symmetric Functions and Hall polynomials, 2nd edition, Clarendon Press, Oxford, 1995.
31. A. Okounkov, “On the representations of the infinite symmetric group,” Available at math.RT/9803037 at xxx.lanl.gov.
32. C. Reutenauer, Free Lie Algebras, London Mathematical Society Monographs. New Series
7. Clarendon Press and Oxford University Press, New York, 1993.
33. B. Sagan, The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd edition, Springer-Verlag, New York, 2001.
34. S. Shnider and S. Sternberg, Quantum Groups. Graduate Texts in Mathematical Physics, II. International Press, 1993.
35. R. Stanley, “Generalized riffle shuffles and quasisymmetric functions,” Preprint math.CO/9912025 at xxx.lanl.gov.
36. R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, New York/Cambridge, 1999.
37. J. Stembridge, “Shifted tableaux and the projective representations of the symmetric groups,” Adv. in Math. 74 (1989), 87-134.
38. J.Y. Thibon, “The cycle enumerator of unimodal permutations,” Preprint math.CO/0102051 at xxx.lanl.gov.
39. 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.
40. A. Vershik and A. Schmidt, “Limit measures arising in the asymptotic theory of symmetric groups,” Prob. Theory. Appl. 22 (1977), 72-88 and 23 (1977), 34-46.