Reduced decompositions and permutation patterns
Bridget Eileen Tenner
Massachusetts Institute of Technology Department of Mathematics 77 Massachusetts Avenue Cambridge MA 02139 USA
DOI: 10.1007/s10801-006-0015-6
Abstract
Billey, Jockusch, and Stanley characterized 321-avoiding permutations by a property of their reduced decompositions. This paper generalizes that result with a detailed study of permutations via their reduced decompositions and the notion of pattern containment. These techniques are used to prove a new characterization of vexillary permutations in terms of their principal dual order ideals in a particular poset. Additionally, the combined frameworks yield several new results about the commutation classes of a permutation. In particular, these describe structural aspects of the corresponding graph of the classes and the zonotopal tilings of a polygon defined by Elnitsky that is associated with the permutation.
Pages: 263–284
Keywords: keywords reduced decomposition; permutation pattern; vexillary permutation; zonotopal tiling; freely braided permutation
Full Text: PDF
References
1. S.C. Billey, W. Jockusch, and R.P. Stanley, “Some combinatorial properties of Schubert polynomials,” J. Alg. Combin. 2 (1993), 345-374.
2. A. Bj\ddot orner, private communication, April 2005.
3. A. Bj\ddot orner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics 231, Springer, New York,
2005. Springer J Algebr Comb (2006) 24:263-284
4. S. Elnitsky, “Rhombic tilings of polygons and classes of reduced words in Coxeter groups,” J. Combin. Theory, Ser. A 77 (1997), 193-221.
5. R.M. Green and J. Losonczy, “Freely braided elements in Coxeter groups,” Ann. Comb. 6 (2002), 337-348.
6. R.M. Green and J. Losonczy, “Freely braided elements in Coxeter groups, II,” Adv. in Appl. Math. 33 (2004), 26-39.
7. L.M. Kelly and R. Rottenberg, “Simple points in pseudoline arrangements,” Pacific J. Math. 40 (1972), 617-622.
8. A. Lascoux and M.P. Sch\ddot utzenberger, “Polyn\hat omes de Schubert,” C. R. Acad. Sci. Paris, Série I 294 (1982), 447-450.
9. I.G. Macdonald, Notes on Schubert Polynomials, Laboratoire de combinatoire et d'informatique mathématique (LACIM), Université du Québec `a Montréal, Montreal, 1991.
10. T. Mansour, “The enumeration of permutations whose posets have a maximal element,” preprint.
11. T. Mansour, “On an open problem of Green and Losonczy: Exact enumeration of freely braided permutations,” Discrete Math. Theor. Comput. Sci. 6 (2004), 461-470.
12. D.V. Pasechnik and B. Shapiro, “In search of higher permutahedra,” preprint.
13. V. Reiner, “Note on the expected number of Yang-Baxter moves applicable to reduced decompositions,” Europ. J. Combin. 26 (2005), 1019-1021.
14. B. Shapiro, M. Shapiro, and A. Vainshtein, “Connected components in the intersection of two open opposite Schubert cells in S Ln(R)/B,” Intern. Math. Res. Notices, no. 10 (1997), 469-493.
15. R. Simion and F.W. Schmidt, “Restricted permutations,” European J. Combin. 6 (1985), 383-406.
16. R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, no. 62, Cambridge University Press, Cambridge, 1999.
17. R.P. Stanley, “On the number of reduced decompositions of elements of Coxeter groups,” European J. Combin. 5 (1984), 359-372.
2. A. Bj\ddot orner, private communication, April 2005.
3. A. Bj\ddot orner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics 231, Springer, New York,
2005. Springer J Algebr Comb (2006) 24:263-284
4. S. Elnitsky, “Rhombic tilings of polygons and classes of reduced words in Coxeter groups,” J. Combin. Theory, Ser. A 77 (1997), 193-221.
5. R.M. Green and J. Losonczy, “Freely braided elements in Coxeter groups,” Ann. Comb. 6 (2002), 337-348.
6. R.M. Green and J. Losonczy, “Freely braided elements in Coxeter groups, II,” Adv. in Appl. Math. 33 (2004), 26-39.
7. L.M. Kelly and R. Rottenberg, “Simple points in pseudoline arrangements,” Pacific J. Math. 40 (1972), 617-622.
8. A. Lascoux and M.P. Sch\ddot utzenberger, “Polyn\hat omes de Schubert,” C. R. Acad. Sci. Paris, Série I 294 (1982), 447-450.
9. I.G. Macdonald, Notes on Schubert Polynomials, Laboratoire de combinatoire et d'informatique mathématique (LACIM), Université du Québec `a Montréal, Montreal, 1991.
10. T. Mansour, “The enumeration of permutations whose posets have a maximal element,” preprint.
11. T. Mansour, “On an open problem of Green and Losonczy: Exact enumeration of freely braided permutations,” Discrete Math. Theor. Comput. Sci. 6 (2004), 461-470.
12. D.V. Pasechnik and B. Shapiro, “In search of higher permutahedra,” preprint.
13. V. Reiner, “Note on the expected number of Yang-Baxter moves applicable to reduced decompositions,” Europ. J. Combin. 26 (2005), 1019-1021.
14. B. Shapiro, M. Shapiro, and A. Vainshtein, “Connected components in the intersection of two open opposite Schubert cells in S Ln(R)/B,” Intern. Math. Res. Notices, no. 10 (1997), 469-493.
15. R. Simion and F.W. Schmidt, “Restricted permutations,” European J. Combin. 6 (1985), 383-406.
16. R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, no. 62, Cambridge University Press, Cambridge, 1999.
17. R.P. Stanley, “On the number of reduced decompositions of elements of Coxeter groups,” European J. Combin. 5 (1984), 359-372.