Proceedings of the American Mathematical Society

Author(s): W. M. B. Dukes; V\’ it Jel\’ inek; Toufik Mansour; Astrid Reifegerste
Journal: Proc. Amer. Math. Soc. 137 (2009), 457-465.
MSC (2000): Primary 05A15; Secondary 05A05
Posted: July 9, 2008
Retrieve article in: PDF

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

, and

for involutions.

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 -hexagon-avoiding permutations, J. Algebraic Combin. 13 (2001), no. 2, 111-136. MR 1826948 (2002f:05161)
8.: M. Bóna, Symmetry and unimodality in -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, www.ams.org/amsmtgs/2098_abstracts/1023-05-1618.pdf, 2007.
16.: V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in , Proc. Indian Acad. Sci. Math. Sci. 100 (1990), 45-52. MR 1051089 (91c:14061)
17.: T. Mansour, http://www.math.haifa.ac.il/toufik/enum2005.html, 2007.
18.: T. Mansour and A. Vainshtein, Avoiding maximal parabolic subgroups of , 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)

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

W. M. B. Dukes
Affiliation: Science Institute, University of Iceland, Reykjav\’ ik, Iceland
Email: dukes@raunvis.hi.is

V\’ it Jel\’ inek
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

DOI: 10.1090/S0002-9939-08-09492-6
PII: S 0002-9939(08)09492-6
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
Posted: 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 of article: Copyright 2008, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS