DMTCS Proceedings, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)

Font Size:  Small  Medium  Large

Modified Growth Diagrams, Permutation Pivots, and the BWX Map φ*

Jonathan Bloom, Dan Saracino


In their paper on Wilf-equivalence for singleton classes, Backelin, West, and Xin introduced a transformation φ*, defined by an iterative process and operating on (all) full rook placements on Ferrers boards. Bousquet-Mélou and Steingr&\'i;msson proved the analogue of the main result of Backelin, West, and Xin in the context of involutions, and in so doing they needed to prove that φ* commutes with the operation of taking inverses. The proof of this commutation result was long and difficult, and Bousquet-Mélou and Steingr&\'i;msson asked if φ* might be reformulated in such a way as to make this result obvious. In the present paper we provide such a reformulation of φ*, by modifying the growth diagram algorithm of Fomin. This also answers a question of Krattenthaler, who noted that a bijection defined by the unmodified Fomin algorithm obviously commutes with inverses, and asked what the connection is between this bijection and φ*.
Résumé. Dans leur article sur l'équivalence de Wilf pour les classes de singletons, Backelin, West et Xin ont introduit une transformation φ*, définie par un processus itératif et opérant sur (tous) les placements complets de tours sur un plateau de Ferrers. Bousquet-Melou et Ste&\'i;ngrimsson ont démontré l'analogue du résultat principal de Backelin, West et Xin dans le contexte d'involutions, et pour ce faire ont eu besoin de démontrer que φ* commute avec l'opération inverse. La preuve de cette commutativité est longue et difficile, et Bousquet-Melou et Steingrömsson se demandèrent s'il n'était pas possible de reformuler φ* de sorte que le resultat devienne évident. Dans le présent article, nous proposons une telle reformulation de φ*, en modifiant l'algorithme de croissance de diagramme de Fomin. Cette reformulation répond également à une question de Krattenthaler, qui, remarquant qu'une bijection définie par l'algorithme de Fomin non modifié commute évidemment avec l'opération inverse, se demanda quel était le rapport entre cette bijection et φ*.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional