Modified Growth Diagrams, Permutation Pivots, and the BXW map $ϕ^*$
Jonathan Bloom, Dan Saracino · arXiv (Cornell University) · 2011
In their paper [1] on Wilf-equivalence for singleton classes, Backelin, Xin, and West introduce a transformation $ϕ^*$, defined by an iterative process and operating on (all) full rook placements on Ferrers boards. In [3], Bousquet-M$\acute{\textrm{e}}$lou and Steingr$\acute{\textrmı}$msson prove the analogue of the main result of [1] in the context of involutions, and in so doing they must prove that $ϕ^*$ commutes with the operation of taking inverses. The proof of this commutation result is long and difficult, and Bousquet-M$\acute{\textrm{e}}$lou and Steingr$\acute{\textrmı}$msson ask 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 [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 $ϕ^*$.