Schensted Algorithms for Dual Graded Graphs

This paper is a sequel to 3]. We keep the notation and terminology and extend the numbering of sections, propositions, and formulae of 3].The main result of this paper is a generalization of the Robinson-Schensted correspondence to the class of dual graded graphs introduced in 3], This class extends the class of Y-graphs, or differential posets 22], for which a generalized Schensted correspondence was constructed earlier in 2].The main construction leads to unified bijective proofs of various identities related to path counting, including those obtained in 3]. It is also applied to permutation enumeration, including rook placements on Ferrers boards and enumeration of involutions.As particular cases of the general construction, we re-derive the classical algorithm of Robinson, Schensted, and Knuth 19, 12], the Sagan-Stanley 18], Sagan-Worley 16, 29] and Haiman's 11] algorithms and the author's algorithm for the Young-Fibonacci graph 2]. Some new applications are suggested.The rim hook correspondence of Stanton and White 23] and Viennot's bijection 28] are also special cases of the general construction of this paper.In 5], the results of this paper and the previous paper 3] were presented in a form of extended abstract.