Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



New equivalences for pattern avoiding involutions

Authors: W. M. B. Dukes, V\’ it Jel\’ inek, Toufik Mansour and Astrid Reifegerste
Journal: Proc. Amer. Math. Soc. 137 (2009), 457-465
MSC (2000): Primary 05A15; Secondary 05A05
Published electronically: July 9, 2008
MathSciNet review: 2448564
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. J. Backelin, J. West, and G. Xin, Wilf-equivalence for singleton classes, Adv. Appl. Math. 38 (2007), no. 2, 133-148. MR 2290807 (2007i:05002)
  • 2. D.A. Beck, The combinatorics of symmetric functions and permutation enumeration of the hyperoctahedral group, Discrete Math. 163 (1997), 13-45. MR 1428556 (98f:05149)
  • 3. S.C. Billey, Pattern avoidance and rational smoothness of Schubert varieties, Adv. Math. 139 (1998), 141-156. MR 1652522 (99i:14058)
  • 4. S. Billey, W. Jockusch and R.P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), 345-374. MR 1241505 (94m:05197)
  • 5. S. Billey and T. Kai Lam, Vexillary elements in the hyperoctahedral group, J. Algebraic Combin. 8 (1998), 139-152. MR 1648468 (2000d:05124)
  • 6. S. Billey and V. Lakshmibai, On the singular locus of a Schubert variety, J. Ramanujan Math. Soc. 15 (2000), no. 3, 155-223. MR 1789826 (2001m:14074)
  • 7. S. Billey and G. Warrington, Kazhdan-Lusztig polynomials for $ 321$-hexagon-avoiding permutations, J. Algebraic Combin. 13 (2001), no. 2, 111-136. MR 1826948 (2002f:05161)
  • 8. M. Bóna, Symmetry and unimodality in $ t$-stack sortable permutations, J. Combin. Theory Ser. A 98 (2002), 201-209. MR 1897934 (2003g:05007a)
  • 9. M. Bóna, A survey of stack-sorting disciplines, Electron. J. Combin. 9:2 (2002), #A1. MR 2028290 (2004j:05012)
  • 10. M. Bousquet-Mélou, Multi-statistic enumeration of two-stack sortable permutations, Electron. J. Combin. 5 (1998), #R21. MR 1614300 (99b:05001)
  • 11. M. Bousquet-Mélou and E. Steingrímsson, Decreasing subsequences in permutations and Wilf equivalence for involutions, J. Alg. Comb. 22 (2005), 383-409. MR 2191644 (2006j:05002)
  • 12. Mark Dukes, Vít Jelínek, Toufik Mansour and Astrid Reifegerste, New equivalences for pattern avoiding involutions, arXiv:0708.1357, 2007.
  • 13. 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.
  • 14. A.D. Jaggard, Prefix exchanging and pattern avoidance by involutions, Electronic J. Comb. 9 (2003), #R16. MR 2028285 (2005b:05008)
  • 15. A.D. Jaggard and J.J. Marincel, Generating tree isomorphisms for pattern-avoiding involutions,, 2007.
  • 16. V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in $ {Sl}(n)/B$, Proc. Indian Acad. Sci. Math. Sci. 100 (1990), 45-52. MR 1051089 (91c:14061)
  • 17. T. Mansour,, 2007.
  • 18. T. Mansour and A. Vainshtein, Avoiding maximal parabolic subgroups of $ S_k$, Discrete Math. Theor. Comput. Sci. 4 (2000), 67-77. MR 1798705 (2001k:05016)
  • 19. T. Mansour and A. Vainshtein, Restricted permutations and Chebyshev polynomials, Sém. Lothar. Combin. 47 (2002), Article B47c. MR 1894023 (2003a:05003)
  • 20. R. Tarjan, Sorting using networks of queues and stacks, J. Assoc. Comput. Mach. 19 (1972), 341-346. MR 0298803 (45:7852)
  • 21. J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge (1990).
  • 22. J. West, Sorting twice through a stack, Theoret. Comput. Sci. 117 (1993), 303-313. MR 1235186 (94j:68045)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05A15, 05A05

Retrieve articles in all journals with MSC (2000): 05A15, 05A05

Additional Information

W. M. B. Dukes
Affiliation: Science Institute, University of Iceland, Reykjavík, Iceland

V\’ it Jel\’ inek
Affiliation: Department of Applied Mathematics, Charles University, Prague, Czech Republic

Toufik Mansour
Affiliation: Department of Mathematics, University of Haifa, 31905 Haifa, Israel

Astrid Reifegerste
Affiliation: Faculty of Mathematics, University of Magdeburg, Magdeburg, Germany

Keywords: Forbidden subsequences, pattern avoiding permutations, pattern avoiding involutions, signed permutations, Wilf equivalence
Received by editor(s): November 21, 2007
Received by editor(s) in revised form: January 22, 2008
Published electronically: July 9, 2008
Additional Notes: The second author was supported by project 201/05/H014 of the Czech Science Foundation and project MSM0021620838 of the Czech Ministry of Education.
Communicated by: Jim Haglund
Article copyright: © Copyright 2008 American Mathematical Society

American Mathematical Society