Bijections between pattern-avoiding fillings of Young diagrams

DOI10.1016/J.JCTA.2010.03.006MaRDI QIDQ1957976zbMATH OpenOpenAlexWikidataFDO

Authors Matthieu Josuat-Vergés

Publication date 27 September 2010

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.4928

zbMATH Keywords

acyclic orientationsfillingspattern avoiding fillingpermutation tableauxpolyominoesYoung diagrams

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of representation theory (05E10)

Abstract: The pattern-avoiding fillings of Young diagrams we study arose from Postnikov's work on positive Grassman cells. They are called Le-diagrams, and are in bijection with decorated permutations. Other closely-related diagrams are interpreted as acyclic orientations of some bipartite graphs. The definition of the diagrams is the same but the avoided patterns are different. We give here bijections proving that the number of pattern-avoiding filling of a Young diagram is the same, for these two different sets of patterns. The result was obtained by Postnikov via a reccurence relation. This relation was extended by Spiridonov to obtain more general results about other patterns and other polyominoes than Young diagrams, and we show that our bijections also extend to more general polyominoes.

Recommendations

• Pattern-avoidance in binary fillings of grid shapes (short version)
• Ascent-descent Young diagrams and pattern avoidance in alternating permutations
• On the diagram of 132-avoiding permutations
• Pattern avoidance and Young tableaux
• Pattern avoidance in alternating permutations and tableaux (extended abstract)

Cites work

• Acyclic orientations of graphs
• Bijections for permutation tableaux
• Enumeration of totally positive Grassmann cells
• Generalized triangulations and diagonal-free subsets of stack polyominoes
• On some properties of permutation tableaux
• Pattern-avoidance in binary fillings of grid shapes (short version)
• Permutation tableaux and permutation patterns

Cited in

(5)

• An automaton-theoretic approach to the representation theory of quantum algebras
• Lonesum and \(\Gamma\)-free \(0-1\) fillings of Ferrers shapes
• Pattern-avoidance in binary fillings of grid shapes (short version)
• Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
• Combinatorics of diagrams of permutations

This page was built for publication: Bijections between pattern-avoiding fillings of Young diagrams

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