Modified growth diagrams, permutation pivots, and the BWX map ^

DOI10.1016/J.JCTA.2012.03.003MaRDI QIDQ423647zbMATH OpenOpenAlexFDO

Authors Jonathan Bloom, Dan Saracino

Publication date 4 June 2012

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

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

zbMATH Keywords

BWX mapgrowth diagramsKnuth equivalenceKnuth transformationsleft pivotsmodified growth diagramspermutation patternspermutation pivotsright pivots

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: In their paper [1] on Wilf-equivalence for singleton classes, Backelin, Xin, and West introduce a transformation $ph{i}^{\ast }$, defined by an iterative process and operating on (all) full rook placements on Ferrers boards. In [3], Bousquet-M$acuteextrme$lou and Steingr$acuteextrmi$msson prove the analogue of the main result of [1] in the context of involutions, and in so doing they must prove that $ph{i}^{\ast }$ commutes with the operation of taking inverses. The proof of this commutation result is long and difficult, and Bousquet-M$acuteextrme$lou and Steingr$acuteextrmi$msson ask if $ph{i}^{\ast }$ might be reformulated in such a way as to make this result obvious. In the present paper we provide such a reformulation of $ph{i}^{\ast }$, by modifying the growth diagram algorithm of Fomin [4,5]. This also answers a question of Krattenthaler [6, problem 4], who notes that a bijection defined by the unmodified Fomin algorithm obviously commutes with inverses, and asks what the connection is between this bijection and $ph{i}^{\ast }$.

Recommendations

• Modified growth diagrams, permutation pivots, and the BWX map \(\phi^*\)
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
• Another look at bijections for pattern-avoiding permutations
• On two bijections from \(S_{n}(321)\) to \(S_{n}(132)\).

Cites work

• Another look at bijections for pattern-avoiding permutations
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 4079428 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Longest Increasing and Decreasing Subsequences
• On two bijections from \(S_{n}(321)\) to \(S_{n}(132)\).
• Quelques remarques sur une Construction de Schensted.
• Schensted algorithms for dual graded graphs
• Wilf-equivalence for singleton classes

Cited in

(3)

• Maximal increasing sequences in fillings of almost-moon polyominoes
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• Modified growth diagrams, permutation pivots, and the BWX map \(\phi^*\)

This page was built for publication: Modified growth diagrams, permutation pivots, and the BWX map \(\phi ^{\ast}\)

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