Modified growth diagrams, permutation pivots, and the BWX map ϕ⁎

AbstractIn 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í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í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 ϕ⁎