New equivalences for pattern avoiding involutions

Dukes, W.; Jelinek, Vít; Mansour, Toufik; Reifegerste, Astrid

doi:10.1090/S0002-9939-08-09492-6

New equivalences for pattern avoiding involutions
HTML articles powered by AMS MathViewer

by W. M. B. Dukes, Vít Jelinek, Toufik Mansour and Astrid Reifegerste PDF

Proc. Amer. Math. Soc. 137 (2009), 457-465 Request permission

Abstract:

We complete the Wilf classification of signed patterns of length 5 for both signed permutations and signed involutions. New general equivalences of patterns are given which prove Jaggard’s conjectures concerning involutions in the symmetric group avoiding certain patterns of length 5 and 6. In this way, we also complete the Wilf classification of $S_5$, $S_6$, and $S_7$ for involutions.

References

Jörgen Backelin, Julian West, and Guoce Xin, Wilf-equivalence for singleton classes, Adv. in Appl. Math. 38 (2007), no. 2, 133–148. MR 2290807, DOI 10.1016/j.aam.2004.11.006
Desiree A. Beck, The combinatorics of symmetric functions and permutation enumeration of the hyperoctahedral group, Discrete Math. 163 (1997), no. 1-3, 13–45. MR 1428556, DOI 10.1016/0012-365X(95)00326-R
Sara C. Billey, Pattern avoidance and rational smoothness of Schubert varieties, Adv. Math. 139 (1998), no. 1, 141–156. MR 1652522, DOI 10.1006/aima.1998.1744
Sara C. Billey, William Jockusch, and Richard P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), no. 4, 345–374. MR 1241505, DOI 10.1023/A:1022419800503
Sara Billey and Tao Kai Lam, Vexillary elements in the hyperoctahedral group, J. Algebraic Combin. 8 (1998), no. 2, 139–152. MR 1648468, DOI 10.1023/A:1008633710118
Sara Billey and V. Lakshmibai, On the singular locus of a Schubert variety, J. Ramanujan Math. Soc. 15 (2000), no. 3, 155–223. MR 1789826
Sara C. Billey and Gregory S. Warrington, Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations, J. Algebraic Combin. 13 (2001), no. 2, 111–136. MR 1826948, DOI 10.1023/A:1011279130416
Miklós Bóna, Symmetry and unimodality in $t$-stack sortable permutations, J. Combin. Theory Ser. A 98 (2002), no. 1, 201–209. MR 1897934, DOI 10.1006/jcta.2001.3235
Miklós Bóna, A survey of stack-sorting disciplines, Electron. J. Combin. 9 (2002/03), no. 2, Article 1, 16. Permutation patterns (Otago, 2003). MR 2028290
Mireille Bousquet-Mélou, Multi-statistic enumeration of two-stack sortable permutations, Electron. J. Combin. 5 (1998), Research Paper 21, 12. MR 1614300
Mireille Bousquet-Mélou and Einar Steingrímsson, Decreasing subsequences in permutations and Wilf equivalence for involutions, J. Algebraic Combin. 22 (2005), no. 4, 383–409. MR 2191644, DOI 10.1007/s10801-005-4625-1
Mark Dukes, Vít Jelínek, Toufik Mansour and Astrid Reifegerste, New equivalences for pattern avoiding involutions, arXiv:0708.1357, 2007.
W.M.B. Dukes, T. Mansour, and A. Reifegerste, Wilf classification of three and four letter signed patterns, Discrete Math. 308:15 (2008), 3125–3133.
Aaron D. Jaggard, Prefix exchanging and pattern avoidance by involutions, Electron. J. Combin. 9 (2002/03), no. 2, Research paper 16, 24. Permutation patterns (Otago, 2003). MR 2028285
A.D. Jaggard and J.J. Marincel, Generating tree isomorphisms for pattern-avoiding involutions, www.ams.org/amsmtgs/2098_abstracts/1023-05-1618.pdf, 2007.
V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in $\textrm {Sl}(n)/B$, Proc. Indian Acad. Sci. Math. Sci. 100 (1990), no. 1, 45–52. MR 1051089, DOI 10.1007/BF02881113
T. Mansour, http://www.math.haifa.ac.il/toufik/enum2005.html, 2007.
Toufik Mansour and Alek Vainshtein, Avoiding maximal parabolic subgroups of $S_k$, Discrete Math. Theor. Comput. Sci. 4 (2000), no. 1, 67–75. MR 1798705
T. Mansour and A. Vainshtein, Restricted permutations and Chebyshev polynomials, Sém. Lothar. Combin. 47 (2001/02), Art. B47c, 17. MR 1894023
Robert Tarjan, Sorting using networks of queues and stacks, J. Assoc. Comput. Mach. 19 (1972), 341–346. MR 298803, DOI 10.1145/321694.321704
J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge (1990).
Julian West, Sorting twice through a stack, Theoret. Comput. Sci. 117 (1993), no. 1-2, 303–313. Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991). MR 1235186, DOI 10.1016/0304-3975(93)90321-J