# zbMATH — the first resource for mathematics

Schensted algorithms for dual graded graphs. (English) Zbl 0817.05077
From the author’s abstract: This paper is a sequel to the author’s paper [Duality of graded graphs, J. Algebr. Comb. 3, No. 4, 357-404 (1994; Zbl 0810.05005)]. The main result is a generalization of the Robinson- Schensted correspondence to the class of dual graded graphs. This class extends the class of $$Y$$-graphs, or differential posets, for which a generalized Schensted correspondence was constructed earlier. The main construction leads to unified bijective proofs of various identities related to path counting. It is also applied to permutation enumeration, including rook placements on Ferrers boards and enumeration of involutions.
As particular cases of the general construction the classical algorithm of Robinson, Schensted, and Knuth, the Sagan-Stanley, Sagan-Worley and Haiman’s algorithms and the author’s algorithm for the Young-Fibonacci graph are re-derived. Some new application are suggested. The rim hook correspondence of Stanton and White and Viennot’s bijection are also special cases of the general construction of this paper.
Reviewer: K.Engel (Rostock)

##### MSC:
 05E10 Combinatorial aspects of representation theory 05A15 Exact enumeration problems, generating functions 06A07 Combinatorics of partially ordered sets
Full Text:
##### References:
 [1] S.V. Fomin, “Two-dimensional growth in Dedekind lattices,” M. S. thesis, Leningrad State University, 1979. [2] Fomin, S. V., Generalized Robinson-Schensted-Knuth correspondence, Zapiski Nauchn. Sem. LOMI, 155, 156-175, (1986) · Zbl 0661.05004 [3] Fomin, S., Duality of graded graphs, Institut Mittag-Leffler, 3, 357-404, (1992) · Zbl 0810.05005 [4] S. Fomin, Schensted algorithms for dual graded graphs, Report No. 16 (1991/92), Institut Mittag-Leffler, 1992. · Zbl 0817.05077 [5] S. Fomin, Dual graphs and Schensted correspondences, Séries formelles et combinatoire algébrique, P. Leroux and C. Reutenauer, Ed., Montréal, LACIM, UQAM, 1992, 221-236. [6] Fomin, D. V.; Fomin, S. V., Problem 1240, Kvant, 1, 22-25, (1991) [7] S. Fomin and D. Stanton, Rim hook lattices, Report No. 23 (1991/92), Institut Mittag-Leffler, 1992. · Zbl 0897.05086 [8] C. Greene, An extension of Schensted’s theorem, Adv. in Math., 14, 254-265, (1974) · Zbl 0303.05006 [9] Greene, C.; Kleitman, D. J., The structure of Sperner $$k$$-families, J. Combin. Theory, Ser. A, 20, 41-68, (1976) · Zbl 0355.05027 [10] Greene, C., Some partitions associated with a partially ordered set, J. Combin. Theory, Ser. A, 20, 69-79, (1976) · Zbl 0323.06002 [11] Haiman, M. D., On mixed insertion, symmetry, and shifted Young tableaux, J.Combin. Theory, Ser. A, 50, 196-225, (1989) · Zbl 0697.05005 [12] Knuth, D. E., Permutations, matrices, and generalized Young tableaux, Pacific J. Math., 34, 709-727, (1970) · Zbl 0199.31901 [13] I.G. Macdonald, Symmetric functions and Hall polynomials, Oxford Univ. Press, Oxford, 1979. · Zbl 0487.20007 [14] J. Riordan, An introduction to combinatorial analysis, Wiley, New York, 1966. [15] T.W. Roby, “Applications and extensions of Fomin”s generalization of the Robinson-Schensted correspondence to differential posets,” Ph.D. thesis, M.I.T., 1991. [16] Sagan, B. E., Shifted tableaux, Schur $$Q$$-functions and a conjecture of R. Stanley, J. Comb. Theory, Ser. A, 45, 62-103, (1987) · Zbl 0661.05010 [17] B.E. Sagan, “The ubiquitous Young tableaux,” Invariant Theory and Tableaux, D. Stanton, Ed., Springer-Verlag, 1990, 262-298. [18] Sagan, B. E.; Stanley, R. P., Robinson-Schensted algorithms for skew tableaux, J.Combin. Theory, Ser. A, 55, 161-193, (1990) · Zbl 0732.05061 [19] Schensted, C., Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191, (1961) · Zbl 0097.25202 [20] M.-P. Schützenberger, “La correspondence de Robinson,” Combinatoire et représentation du groupe symétrique, D. Foata ed., Lecture Notes in Math.579 (1977), 59-135. [21] Stanley, R. P., Theory and application of plane partitions, Studies in Applied Math., 50, 167-188, (1971) · Zbl 0225.05011 [22] Stanley, R. P., Differential posets, J. Amer. Math. Soc., 1, 919-961, (1988) · Zbl 0658.05006 [23] Stanton, D.; White, D., A Schensted algorithm for rim hook tableaux, J. Comb. Theory, Ser. A, 40, 211-247, (1985) · Zbl 0577.05001 [24] D. Stanton and D. White, Constructive combinatorics, Springer-Verlag, 1986. [25] S. Sundaram, “On the combinatorics of representations of Sp$$(2n,$$ ℂ)),” Ph.D. thesis, M.I.T., 1986. [26] M.A.A. van Leeuwen, “A Robinson-Schensted algorithm in the geometry of flags for classical groups,” Thesis, Rijksuniversiteit Utrecht, 1989. [27] M.A.A. van Leeuwen, New proofs concerning the Robinson-Schensted and Schützenberger algorithms, Preprint Nr. 700, Utrecht University, Dept. Mathematics, 1991. [28] Viennot, X. G., Maximal chains of subwords and up-down sequences of permutations, J. Comb. Theory, Ser. A, 34, 1-14, (1983) · Zbl 0518.05006 [29] D.R. Worley, “A theory of shifted Young tableaux,” Ph.D. thesis, M.I.T., 1984.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.