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;
(2) bijective proofs of these identities;
(3) design and analysis of algorithms establishing corresponding bijections.
This article is devoted to (1); its sequel [7] is concerned with the problems (2)–(3). A simplified treatment of some of these results can be found in [8].
In this article, R.P. Stanley's [26, 27] linear-algebraic approach to (1) is extended to cover a wide range of graded graphs. The main idea is to consider pairs of graded graphs with a common set of vertices and common rank function. Such graphs are said to be dual if the associated linear operators satisfy a certain commutation relation (e.g., the “Heisenberg” one). The algebraic consequences of these relations are then interpreted as combinatorial identities. (This idea is also implicit in [27].)
[7] contains applications to various examples of graded graphs, including the Young, Fibonacci, Young-Fibonacci and Pascal lattices, the graph of shifted shapes, the r-nary trees, the Schensted graph, the lattice of finite binary trees, etc. Many enumerative identities (both known and unknown) are obtained.
Abstract of [7]. These identities can also be derived in a purely combinatorial way by generalizing the Robinson-Schensted correspondence to the class of graphs under consideration (cf. [5]). The same tools can be applied to permutation enumeration, including involution counting and rook polynomials for Ferrers boards. The bijective correspondences mentioned above are naturally constructed by Schensted-type algorithms. A general approach to these constructions is given. As particular cases we rederive the classical algorithm of Robinson, Schensted, and Knuth [20, 12, 21], the Sagan-Worley [17, 32] and Haiman [11] algorithms, the algorithm for the Young-Fibonacci graph [5, 15], and others. Several new applications are given.
Article PDF
Similar content being viewed by others
References
Aigner, M, Combinatorial Theory, Springer-Verlag, 1979.
Birkhoff, G., Lattice Theory, 3rd ed., Amer. Math. Soc., Providence, RI, 1967.
Björner, A., “The Möbius function of subword order,” Invariant Theory and Tableaux, D. Stanton, Ed., Springer-Verlag, 1990, 118–124.
Fomin, S.V., Two-dimensional growth in Dedekind lattices, M. Sc. thesis, Leningrad State University, 1979.
Fomin, S.V., “Generalized Robinson-Schensted-Knuth correspondence” [in Russian], Zapiski Nauchn. Sem. LOMI 155 (1986), 156–175.
Fomin, S., Duality of graded graphs, Report No. 15 (1991/92), Institut Mittag-Leffler, 1992.
Fomin, S., Schensted algorithms for dual graded graphs, J. Alg. Comb., to appear, Report No. 16 (1991/92), Institut Mittag-Leffler, 1992.
Fomin, S., “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.
Fomin, S. and Stanton, D., Rim hook lattices, Report No. 23 (1991/92), Institut Mittag-Leffler, 1992.
Greene, C., “An extension of Schensted's theorem,” Adv. in Math. 14 (1974), 254–265.
Haiman, M.D., “On mixed insertion, symmetry, and shifted Young tableaux,” J. Combin. Theory, Ser. A 50 (1989), 196–225.
Knuth, D.E., “Permutations, matrices, and generalized Young tableaux,” Pacific J. Math. 34 (1970), 709–727.
Macdonald, I.G., Symmetric Functions and Hall Polynomials, Oxford Univ. Press, Oxford, 1979.
Propp, J., “Some variants of Ferrers diagrams,”J. Combin. Theory, Ser. A 52 (1989), 98–128.
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.
Sagan, B.E., “An analog of Schensted's algorithm for shifted Young tableaux,” J. Comb. Theory, Ser. A 27 (1979), 10–18.
Sagan, B.E., “Shifted tableaux, Schur Q-functions and a conjecture of R. Stanley,” J. Comb. Theory, Ser. A 45 (1987), 62–103.
Sagan, B.E., “The ubiquitous Young tableaux,” Invariant Theory and Tableaux, D. Stanton, Ed., Springer-Verlag, 1990, 262–298.
Schur, I., “Über die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrochene lineare Substitutionen,” J. Reine Angew. Math. 139 (1911), 155–250.
Schensted, C., “Longest increasing and decreasing subsequences,” Canad. J. Math. 13 (1961), 179–191.
Schützenberger, M.-P., “La correspondence de Robinson,” Combinatoire et représentation du groupe symétrique, D. Foata ed., Lecture Notes in Math. 579 (1977), 59–135.
Stanley, R.P., “Theory and application of plane partitions, ” Parts 1 and 2, Studies in Applied Math. 50 (1971), 167–188, 259–279.
Stanley, R.P., “Ordered structures and partitions,” Mem. Amer. Math. Soc. 119 (1972).
Stanley, R.P., “The Fibonacci lattice,” Fibonacci Quart. 13 (1975), 215–232.
Stanley, R.P., Enumerative Combinatorics, vol. I, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.
Stanley, R.P., “Differential posets,” J. Amer. Math. Soc. 1 (1988), 919–961.
Stanley, R.P., “Variations on differential posets,” Invariant Theory and Tableaux, D. Stanton, Ed., Springer-Verlag, 1990, 145–165.
Stanley, R.P., “Further combinatorial properties of two Fibonacci lattices,” Europ. J. Combinatorics 11 (1990), 181–188.
Stanley, R.P., “Problem 90-2,” Mathem. Intelligencer 12 (1990), No. 4, 65.
Stanton, D. and White, D., Constructive Combinatorics, Springer-Verlag, 1986.
Wilkinson, J.H., The Algebraic Eigenvalue Problem, Oxford University Press, Oxford, 1988.
Worley, D.R., A theory of shifted Young tableaux, Ph.D. thesis, M.I.T., 1984.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Fomin, S. Duality of Graded Graphs. Journal of Algebraic Combinatorics 3, 357–404 (1994). https://doi.org/10.1023/A:1022412010826
Issue Date:
DOI: https://doi.org/10.1023/A:1022412010826