Duality of Graded Graphs
Sergey Fomin
DOI: 10.1023/A:1022412010826
Abstract
A graph is said to be graded if its vertices are divided into levels numbered by integers, so that the endpoints of any edge lie on consecutive levels. Discrete modular lattices and rooted trees are among the typical examples. The following three types of problems are of interest to us:
(1) path counting in graded graphs, and related combinatorial identities;
Pages: 357–404
Keywords: enumerative combinatorics; tableaux; Young diagram; differential poset; graded graph
Full Text: PDF
References
1. Aigner, M, Combinatorial Theory, Springer-Verlag, 1979 .
2. Birkhoff, G., Lattice Theory, 3rd ed., Amer. Math. Soc., Providence, RI, 1967.
3. BjOrner, A., "The MObius function of subword order," Invariant Theory and Tableaux, D. Stanton, Ed., Springer-Verlag, 1990, 118-124.
4. Fomin, S.V., Two-dimensional growth in Dedekind lattices, M. Sc. thesis, Leningrad State University, 1979.
5. Fomin, S.V., "Generalized Robinson-Schensted-Knuth correspondence" [in Russian], Zapiski Nauchn. Sem. LOMI 155 (1986), 156-175. FOMIN
6. Fomin, S., Duality of graded graphs, Report No. 15 (1991/92), Institut Mittag-Leffler, 1992.
7. Fomin, S., Schensted algorithms for dual graded graphs, J. Alg. Comb., to appear, Report No. 16 (1991/92), Institut Mittag-Leffler, 1992.
8. Fomin, S., "Dual graphs and Schensted correspondences," Series formelles et combinatoire algtbrique, P. Leroux and C. Reutenauer, Ed., Montreal, LACIM, UQAM, 1992,221-236.
9. Fomin, S. and Stanton, D., Rim hook lattices, Report No. 23 (1991/92), Institut Mittag-Leffler, 1992.
10. Greene, C., "An extension of Schensted's theorem," Adv. in Math. 14 (1974), 254-265.
11. Haiman, M.D., "On mixed insertion, symmetry, and shifted Young tableaux," J. Combin. Theory, Ser. A 50 (1989), 196-225.
12. Knuth, D.E., "Permutations, matrices, and generalized Young tableaux," Pacific J. Math. 34 (1970), 709-727.
13. Macdonald, I.G., Symmetric Functions and Hall Polynomials, Oxford Univ. Press , Oxford, 1979.
14. Propp, J., "Some variants of Ferrers diagrams,"/. Combin. Theory, Ser. A 52 (1989), 98-128.
15. Roby, T.W., 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., "An analog of Schensted's algorithm for shifted Young tableaux," J. Comb. Theory, Ser. A 27 (1979), 10-18.
17. Sagan, B.E., "Shifted tableaux, Schur Q-functions and a conjecture of R. Stanley," J. Comb. Theory, Ser. A 45 (1987), 62-103.
18. Sagan, B.E., "The ubiquitous Young tableaux," Invariant Theory and Tableaux, D. Stanton, Ed., Springer- Verlag, 1990,262-298.
19. Schur, I., "Uber die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrochene lineare Substitutionen," J. Reine Angew. Math. 139 (1911), 155-250.
20. Schensted, C., "Longest increasing and decreasing subsequences," Canad. J. Math. 13 (1961), 179-191.
21. Schfltzenberger, M.-P., "La correspondence de Robinson," Combinatoire et representation du groupe symfrrique, D. Foata ed., Lecture Notes in Math. 579 (1977), 59-135.
22. Stanley, R.P., "Theory and application of plane partitions," Parts 1 and 2, Studies in Applied Math. 50 (1971), 167-188,259-279.
23. Stanley, R.P., "Ordered structures and partitions," Mem. Amer. Math. Soc. 119 (1972).
24. Stanley, R.P., "The Fibonacci lattice," Fibonacci Quart. 13 (1975), 215-232.
25. Stanley, R.P., Enumerative Combinatorics, vol. I, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.
26. Stanley, R.P., "Differential posets," J. Amer. Math. Soc. 1 (1988), 919-961.
27. Stanley, R.P., "Variations on differential posets," Invariant Theory and Tableaux, D. Stanton, Ed., Springer- Verlag, 1990, 145-165.
28. Stanley, R.P., "Further combinatorial properties of two Fibonacci lattices," Europ. J. Combinatorics 11 (1990), 181-188.
29. Stanley, R.P., "Problem 90-2," Mathem. Intelligencer 12 (1990), No. 4,65.
30. Stanton, D. and White, D., Constructive Combinatorics, Springer-Verlag, 1986.
31. Wilkinson, J.H., The Algebraic Eigenvalue Problem, Oxford University Press, Oxford, 1988.
32. Worley, D.R., A theory of shifted Young tableaux, Ph.D. thesis, M.I.T., 1984.
2. Birkhoff, G., Lattice Theory, 3rd ed., Amer. Math. Soc., Providence, RI, 1967.
3. BjOrner, A., "The MObius function of subword order," Invariant Theory and Tableaux, D. Stanton, Ed., Springer-Verlag, 1990, 118-124.
4. Fomin, S.V., Two-dimensional growth in Dedekind lattices, M. Sc. thesis, Leningrad State University, 1979.
5. Fomin, S.V., "Generalized Robinson-Schensted-Knuth correspondence" [in Russian], Zapiski Nauchn. Sem. LOMI 155 (1986), 156-175. FOMIN
6. Fomin, S., Duality of graded graphs, Report No. 15 (1991/92), Institut Mittag-Leffler, 1992.
7. Fomin, S., Schensted algorithms for dual graded graphs, J. Alg. Comb., to appear, Report No. 16 (1991/92), Institut Mittag-Leffler, 1992.
8. Fomin, S., "Dual graphs and Schensted correspondences," Series formelles et combinatoire algtbrique, P. Leroux and C. Reutenauer, Ed., Montreal, LACIM, UQAM, 1992,221-236.
9. Fomin, S. and Stanton, D., Rim hook lattices, Report No. 23 (1991/92), Institut Mittag-Leffler, 1992.
10. Greene, C., "An extension of Schensted's theorem," Adv. in Math. 14 (1974), 254-265.
11. Haiman, M.D., "On mixed insertion, symmetry, and shifted Young tableaux," J. Combin. Theory, Ser. A 50 (1989), 196-225.
12. Knuth, D.E., "Permutations, matrices, and generalized Young tableaux," Pacific J. Math. 34 (1970), 709-727.
13. Macdonald, I.G., Symmetric Functions and Hall Polynomials, Oxford Univ. Press , Oxford, 1979.
14. Propp, J., "Some variants of Ferrers diagrams,"/. Combin. Theory, Ser. A 52 (1989), 98-128.
15. Roby, T.W., 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., "An analog of Schensted's algorithm for shifted Young tableaux," J. Comb. Theory, Ser. A 27 (1979), 10-18.
17. Sagan, B.E., "Shifted tableaux, Schur Q-functions and a conjecture of R. Stanley," J. Comb. Theory, Ser. A 45 (1987), 62-103.
18. Sagan, B.E., "The ubiquitous Young tableaux," Invariant Theory and Tableaux, D. Stanton, Ed., Springer- Verlag, 1990,262-298.
19. Schur, I., "Uber die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrochene lineare Substitutionen," J. Reine Angew. Math. 139 (1911), 155-250.
20. Schensted, C., "Longest increasing and decreasing subsequences," Canad. J. Math. 13 (1961), 179-191.
21. Schfltzenberger, M.-P., "La correspondence de Robinson," Combinatoire et representation du groupe symfrrique, D. Foata ed., Lecture Notes in Math. 579 (1977), 59-135.
22. Stanley, R.P., "Theory and application of plane partitions," Parts 1 and 2, Studies in Applied Math. 50 (1971), 167-188,259-279.
23. Stanley, R.P., "Ordered structures and partitions," Mem. Amer. Math. Soc. 119 (1972).
24. Stanley, R.P., "The Fibonacci lattice," Fibonacci Quart. 13 (1975), 215-232.
25. Stanley, R.P., Enumerative Combinatorics, vol. I, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.
26. Stanley, R.P., "Differential posets," J. Amer. Math. Soc. 1 (1988), 919-961.
27. Stanley, R.P., "Variations on differential posets," Invariant Theory and Tableaux, D. Stanton, Ed., Springer- Verlag, 1990, 145-165.
28. Stanley, R.P., "Further combinatorial properties of two Fibonacci lattices," Europ. J. Combinatorics 11 (1990), 181-188.
29. Stanley, R.P., "Problem 90-2," Mathem. Intelligencer 12 (1990), No. 4,65.
30. Stanton, D. and White, D., Constructive Combinatorics, Springer-Verlag, 1986.
31. Wilkinson, J.H., The Algebraic Eigenvalue Problem, Oxford University Press, Oxford, 1988.
32. Worley, D.R., A theory of shifted Young tableaux, Ph.D. thesis, M.I.T., 1984.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition