The Bruhat Order on the Involutions of the Symmetric Group
Federico Incitti
DOI: 10.1023/B:JACO.0000048514.62391.f4
Abstract
In this paper we study the partially ordered set of the involutions of the symmetric group S n with the order induced by the Bruhat order of S n. We prove that this is a graded poset, with rank function given by the average of the number of inversions and the number of excedances, and that it is lexicographically shellable, hence Cohen-Macaulay, and Eulerian.
Pages: 243–261
Keywords: symmetric group; Bruhat order; involution; $E$L-shellability; Cohen-Macaulay
Full Text: PDF
References
1. K. Baclawski, “Cohen-Macaulay ordered sets,” J. Algebra 63 (1980), 226-258.
2. A. Bj\ddot orner, A.M. Garsia, and R.P. Stanley, An Introduction to Cohen-Macaulay Partially Ordered Sets, Ordered Sets (Banff., Alta., 1981), pp. 583-615.
3. A. Bj\ddot orner, “Shellable and Cohen-Macaulay partially ordered sets,” Trans. Amer. Math. Soc. 260 (1980), 159-183.
4. A. Bj\ddot orner and M. Wachs, “Bruhat order of Coxeter groups and shellability,” Adv. in Math. 43 (1982), 87-100.
5. V.V. Deodhar, “Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative M\ddot obius function,” Invent. Math. 39(2) (1977), 187-198.
6. R.S. Deodhar and M.K. Srinivasan, “A statistic on involutions,” J. Alg. Combin. 13(2) (2001), 187-198.
7. P.H. Edelman, “The Bruhat order of the symmetric group is lexicographically shellable,” Proc. Amer. Math. Soc. 82 (1981), 355-358.
8. W. Fulton, “Young tableaux,” With Applications to Representation Theory and Geometry, London Mathematical Society Student Texts, 35, Cambridge University Press, Cambridge, 1997.
9. A.M. Garsia, “Combinatorial methods in the theory of Cohen-Macaulay rings,” Adv. in Math. 38(3) (1980), 229-266.
10. M. Hochster, Cohen-Macaulay Rings, Combinatorics, and Simplicial Complexes, Ring Theory II (Proc. Second Conf. Univ. Oklahoma, 1975), pp. 171-223.
11. R.A. Proctor, “Classical Bruhat orders and lexicographic shellability,” J. Algebra 77 (1982), 104-126.
12. N. Reading, “Order dimension, strong Bruhat order and lattice properties for posets,” Order 19 (2002), 73-100.
13. G. Reisner, “Cohen-Macaulay quotients of polynomial rings,” Adv. in Math. 21 (1976), 30-49.
14. R.W. Richardson and T.A. Springer, “The Bruhat order on symmetric varieties,” Geom. Dedicata 35(1-3) (1990), 389-436.
15. R.W. Richardson and T.A. Springer, “Complements to: The Bruhat order on symmetric varieties,” Geom. Dedicata 49(2) (1994), 231-238.
16. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.
17. R.P. Stanley, “Cohen-Macaulay complexes,” Higher Combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), pp. 51-62.
18. R.P. Stanley, “Supersolvable lattices,” Algebra Universalis 2 (1972), 197-217.
19. D.N. Verma, “M\ddot obius inversion for the Bruhat ordering on a Weyl group,” Ann. Sci. École Norm. Sup. 4 (1971), 393-398.
2. A. Bj\ddot orner, A.M. Garsia, and R.P. Stanley, An Introduction to Cohen-Macaulay Partially Ordered Sets, Ordered Sets (Banff., Alta., 1981), pp. 583-615.
3. A. Bj\ddot orner, “Shellable and Cohen-Macaulay partially ordered sets,” Trans. Amer. Math. Soc. 260 (1980), 159-183.
4. A. Bj\ddot orner and M. Wachs, “Bruhat order of Coxeter groups and shellability,” Adv. in Math. 43 (1982), 87-100.
5. V.V. Deodhar, “Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative M\ddot obius function,” Invent. Math. 39(2) (1977), 187-198.
6. R.S. Deodhar and M.K. Srinivasan, “A statistic on involutions,” J. Alg. Combin. 13(2) (2001), 187-198.
7. P.H. Edelman, “The Bruhat order of the symmetric group is lexicographically shellable,” Proc. Amer. Math. Soc. 82 (1981), 355-358.
8. W. Fulton, “Young tableaux,” With Applications to Representation Theory and Geometry, London Mathematical Society Student Texts, 35, Cambridge University Press, Cambridge, 1997.
9. A.M. Garsia, “Combinatorial methods in the theory of Cohen-Macaulay rings,” Adv. in Math. 38(3) (1980), 229-266.
10. M. Hochster, Cohen-Macaulay Rings, Combinatorics, and Simplicial Complexes, Ring Theory II (Proc. Second Conf. Univ. Oklahoma, 1975), pp. 171-223.
11. R.A. Proctor, “Classical Bruhat orders and lexicographic shellability,” J. Algebra 77 (1982), 104-126.
12. N. Reading, “Order dimension, strong Bruhat order and lattice properties for posets,” Order 19 (2002), 73-100.
13. G. Reisner, “Cohen-Macaulay quotients of polynomial rings,” Adv. in Math. 21 (1976), 30-49.
14. R.W. Richardson and T.A. Springer, “The Bruhat order on symmetric varieties,” Geom. Dedicata 35(1-3) (1990), 389-436.
15. R.W. Richardson and T.A. Springer, “Complements to: The Bruhat order on symmetric varieties,” Geom. Dedicata 49(2) (1994), 231-238.
16. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.
17. R.P. Stanley, “Cohen-Macaulay complexes,” Higher Combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), pp. 51-62.
18. R.P. Stanley, “Supersolvable lattices,” Algebra Universalis 2 (1972), 197-217.
19. D.N. Verma, “M\ddot obius inversion for the Bruhat ordering on a Weyl group,” Ann. Sci. École Norm. Sup. 4 (1971), 393-398.