Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux

MaRDI QIDQ396936zbMATH OpenFDO

Authors Nihal Gowravaram, Ravi Jagadeesan

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6796, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p17

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

alternating permutationsdescent type permutationspattern avoidanceshape-Wilf equivalenceWilf equivalence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of representation theory (05E10)

Abstract: We investigate pattern avoidance in alternating permutations and generalizations thereof. First, we study pattern avoidance in an alternating analogue of Young diagrams. In particular, we extend Babson-West's notion of shape-Wilf equivalence to apply to alternating permutations and so generalize results of Backelin-West-Xin and Ouchterlony to alternating permutations. Second, we study pattern avoidance in the more general context of permutations with restricted ascents and descents. We consider a question of Lewis regarding permutations that are the reading words of thickened staircase Young tableaux, that is, permutations that have (k - 1) ascents followed by a descent, followed by (k - 1) ascents, et cetera. We determine the relative sizes of the sets of pattern-avoiding (k - 1)-ascent permutations in terms of the forbidden pattern. Furthermore, we give inequalities in the sizes of sets of pattern-avoiding permutations in this context that arise from further extensions of shape-equivalence type enumerations.

Review text

Summary: We investigate pattern avoidance in alternating permutations and generalizations thereof. First, we study pattern avoidance in an alternating analogue of Young diagrams. In particular, we extend Babson-West's notion of shape-Wilf equivalence to apply to alternating permutations and so generalize results of \textit{J. Backelin} et al. [Adv. Appl. Math. 38, No. 2, 133--148 (2007; Zbl 1127.05002)] and \textit{E. Ouchterlony} [``Pattern avoiding doubly alternating permutations, in: Proceedings of the international conference on formal power series and algebraic combinatorics, FPSAC 2006. 12 p. (2006)] to alternating permutations. Second, we study pattern avoidance in the more general context of permutations with restricted ascents and descents. We consider a question of Lewis regarding permutations that are the reading words of thickened staircase Young tableaux, that is, permutations that have \(k-1\) ascents followed by a descent, followed by \(k-1\) ascents, et cetera. We determine the relative sizes of the sets of pattern-avoiding \((k-1)\)-ascent permutations in terms of the forbidden pattern. Furthermore, inequalities in the sizes of sets of pattern-avoiding permutations in this context arise from further extensions of shape-equivalence type enumerations. This paper is the first of a two-paper series. The second in the series is [the second author, ``Ascent-descent Young diagrams and pattern avoidance in alternating permutations (submitted)].

Recommendations

• Ascent-descent Young diagrams and pattern avoidance in alternating permutations
• Pattern avoidance for alternating permutations and Young tableaux
• Pattern avoidance in alternating permutations and tableaux (extended abstract)
• Alternating permutations with restrictions and standard Young tableaux
• Generating trees and pattern avoidance in alternating permutations

Cites work

• A new class of Wilf-equivalent permutations
• Alternating permutations with restrictions and standard Young tableaux
• Ascent-descent Young diagrams and pattern avoidance in alternating permutations
• Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux
• Coincidental pattern avoidance
• Combinatorics of permutations
• Criterion for smoothness of Schubert varieties in Sl(n)/B
• Generating trees and pattern avoidance in alternating permutations
• Generating trees and the Catalan and Schröder numbers
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations
• On Wilf equivalence for alternating permutations
• Pattern avoidance for alternating permutations and Young tableaux
• Restricted 132-alternating permutations and Chebyshev polynomials
• Restricted permutations
• The permutations 123p₄ p_m and 321p₄ p_m are Wilf-equivalent
• Wilf-equivalence for singleton classes

Cited in

(16)

• Finding the permutations corresponding to a given Young tableau
• On geometry of Young diagrams for Arnold permutations
• Arc permutations
• On a refinement of Wilf-equivalence for permutations
• Schur-concavity for avoidance of increasing subsequences in block-ascending permutations
• Pattern avoidance for alternating permutations and Young tableaux
• Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays
• Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux
• On pattern avoiding alternating permutations
• Ascent-descent Young diagrams and pattern avoidance in alternating permutations
• Alternating permutations with restrictions and standard Young tableaux
• Pattern-avoidance in binary fillings of grid shapes (short version)
• Pattern avoidance in alternating permutations and tableaux (extended abstract)
• Pattern avoiding alternating involutions
• Equidistribution of set-valued statistics on standard Young tableaux and transversals
• Pattern avoidance in partial permutations

This page was built for publication: Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396936)