JOURNAL OF
ALGEBRAIC
COMBINATORICS

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].

1. S.V. Fomin, "Two-dimensional growth in Dedekind lattices," M. S. thesis, Leningrad State University, 1979.
2. S.V. Fomin, "Generalized Robinson-Schensted-Knuth correspondence," Zapiski Nauchn. Sem. LOMI 155 (1986), 156-175 [in Russian],
3. S. Fomin, Duality of graded graphs, Report No. 15 (1991/92), Institut Mittag-Leffler, 1992; J. Algebr. Combinatorics 3 (1994), 357-404.
4. S. Fomin, Schensted algorithms for dual graded graphs, Report No. 16 (1991/92), Institut Mittag-Leffler, 1992.
5. S. Fomin, Dual graphs and Schensted correspondences, Series formelles et combinatoire algebrique, P. Leroux and C. Reutenauer, Ed., Montreal, LACIM, UQAM, 1992, 221-236.
6. D.V. Fomin and S.V. Fomin, Problem 1240, Kvant, 1991, No. 1, 22-25 [in Russian].
7. S. Fomin and D. Stanton, Rim hook lattices, Report No. 23 (1991/92), Institut Mittag-Leffler, 1992.
8. C.Greene, "An extension of Schensted's theorem," Adv. in Math. 14(1974), 254-265.
9. C. Greene and D.J. Kleitman, "The structure of Sperner k-families," J. Combin. Theory, Ser. A 20 (1976), 41-68.
10. C. Greene, "Some partitions associated with a partially ordered set," J. Combin. Theory, Ser. A 20 (1976), 69-79.
11. M.D. Haiman, "On mixed insertion, symmetry, and shifted Young tableaux," J.Combin. Theory, Ser. A 50 (1989), 196-225.
12. D.E. Knuth, "Permutations, matrices, and generalized Young tableaux," Pacific J. Math. 34 (1970), 709-727.
13. I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford Univ. Press, Oxford, 1979.
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. B.E. Sagan, "Shifted tableaux, Schur Q-functions and a conjecture of R. Stanley," J. Comb. Theory, Ser. A 45(1987), 62-103.
17. B.E. Sagan, "The ubiquitous Young tableaux," Invariant Theory and Tableaux, D.Stanton, Ed., Springer- Verlag, 1990, 262-298.
18. B.E. Sagan and R.P. Stanley, "Robinson-Schensted algorithms for skew tableaux," J.Combin. Theory, Ser. A 55 (1990), 161-193.
19. C. Schensted, "Longest increasing and decreasing subsequences," Canad. J. Math. 13 (1961), 179-191.
20. M.-P. Schutzenberger, "La correspondence de Robinson," Combinatoire et representation du groupe symetrique, D. Foata ed., Lecture Notes in Math. 579 (1977), 59-135.
21. R.P. Stanley, "Theory and application of plane partitions," Parts 1 and 2, Studies in Applied Math. 50 (1971), 167-188, 259-279.
22. R.P. Stanley, "Differential posets," J. Amer. Math. Soc. 1 (1988), 919-961.
23. D. Stanton and D. White, "A Schensted algorithm for rim hook tableaux," J. Comb. Theory, Ser. A 40 (1985), 211-247.
24. D. Stanton and D. White, Constructive combinatorics, Springer-Verlag, 1986.
25. S. Sundaram, "On the combinatorics of representations of Sp(2n, C))," 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 Schutzenberger algorithms, Preprint Nr. 700, Utrecht University, Dept. Mathematics, 1991.
28. X.G. Viennot, "Maximal chains of subwords and up-down sequences of permutations," J. Comb. Theory, Ser. A 34 (1983), 1-14.
29. D.R. Worley, "A theory of shifted Young tableaux," Ph.D. thesis, M.I.T., 1984.