## 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

## Additional Information

**W. M. B. Dukes**- Affiliation: Science Institute, University of Iceland, Reykjavík, Iceland
- Email: dukes@raunvis.hi.is
**Vít Jelinek**- Affiliation: Department of Applied Mathematics, Charles University, Prague, Czech Republic
- Email: jelinek@kam.mff.cuni.cz
**Toufik Mansour**- Affiliation: Department of Mathematics, University of Haifa, 31905 Haifa, Israel
- Email: toufik@math.haifa.ac.il
**Astrid Reifegerste**- Affiliation: Faculty of Mathematics, University of Magdeburg, Magdeburg, Germany
- Email: astrid.reifegerste@ovgu.de
- 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
- © Copyright 2008 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**137**(2009), 457-465 - MSC (2000): Primary 05A15; Secondary 05A05
- DOI: https://doi.org/10.1090/S0002-9939-08-09492-6
- MathSciNet review: 2448564