# zbMATH — the first resource for mathematics

Duality of graded graphs. (English) Zbl 0810.05005
A graded graph is a triple $$G= (P,\rho,E)$$ where $$P$$ is a discrete set of vertices, $$\rho: P\to Z$$ is a rank function, $$E$$ is a multiset of arcs/edges $$(x,y)$$ where $$\rho(y)= \rho(x)+ 1$$. The set $$P_ n= \{x: \rho(x)= n\}$$ is called a level of $$G$$. Finiteness of the levels is always assumed and some of them may be empty. The situation when $$P_ 0= \{\widehat 0\}, P_{-1}= P_{-2}=\dots= \varnothing$$ is typical (a graph with a zero $$\widehat 0$$). Let $$e(x\to y)$$ denote the number of shortest non-oriented paths between $$x$$ and $$y$$ and $$\alpha(n\to m)$$ is the number of paths connecting the $$n$$th and $$m$$th levels. One can similarly define $$\alpha(n\to m\to p)$$, $$e(x\to y\to z)$$ etc. In a graph with zero let $$e(y)= e(\widehat 0\to y)$$, so $$e(y)$$ is the number of paths going from $$\widehat 0$$ to $$y$$. The main results of the reviewed paper are combinatorial identities involving $$e(x)$$ and similar enumerative functions. A typical example is the Young-Frobenius identity $$\sum_{x\in P_ n} e(x)^ 2= n!$$, or, equivalently, $$\alpha(0\to n\to 0)= n!$$ for Young’s lattice. This is not an isolated result. A similar identity (with additional coefficients) is known for the graph of shifted shapes, another example is the lattice of binary trees where $$\alpha(0\to n)= n!$$. Each of these facts is known to have both computational and bijective proofs; however, these proofs use individual properties of the graphs. In the paper under review the author develops combinatorial techniques for proving general results of this type for a wide class of graded graphs and gives unified proofs and many other enumerative identities, both known and unknown.

##### MSC:
 05A19 Combinatorial identities, bijective combinatorics 05E10 Combinatorial aspects of representation theory 05C05 Trees 60C05 Combinatorial probability 06A07 Combinatorics of partially ordered sets 06D99 Distributive lattices
Full Text:
##### 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, Zapiski Nauchn. Sem. LOMI, 155, 156-175, (1986) · Zbl 0661.05004  Fomin, S., Duality of graded graphs, Report No. 15 (1991/92), Institut Mittag-Leffler, 1992. · Zbl 0810.05005  Fomin, S., Schensted algorithms for dual graded graphs, J. Alg. Comb., to appear, Report No. 16 (1991/92), Institut Mittag-Leffler, 1992. · Zbl 0817.05077  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. · Zbl 0897.05086  Greene, C., An extension of Schensted’s theorem, Adv. in Math., 14, 254-265, (1974) · Zbl 0303.05006  Haiman, M. D., On mixed insertion, symmetry, and shifted Young tableaux, J. Combin. Theory, 50, 196-225, (1989) · Zbl 0697.05005  Knuth, D. E., Permutations, matrices, and generalized Young tableaux, Pacific J. Math., 34, 709-727, (1970) · Zbl 0199.31901  Macdonald, I.G., Symmetric Functions and Hall Polynomials, Oxford Univ. Press, Oxford, 1979. · Zbl 0487.20007  Propp, J., Some variants of Ferrers diagrams, J. Combin. Theory, 52, 98-128, (1989) · Zbl 0682.05007  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, 27, 10-18, (1979) · Zbl 0428.05005  Sagan, B. E., Shifted tableaux, Schur $$Q$$-functions and a conjecture of R. Stanley, J. Comb. Theory, 45, 62-103, (1987) · Zbl 0661.05010  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. · JFM 42.0154.02  Schensted, C., Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191, (1961) · Zbl 0097.25202  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, Studies in Applied Math., 50, 167-188, (1971) · Zbl 0225.05011  Stanley, R.P., “Ordered structures and partitions,” Mem. Amer. Math. Soc.119 (1972). · Zbl 0246.05007  Stanley, R. P., The Fibonacci lattice, Fibonacci Quart., 13, 215-232, (1975) · Zbl 0328.06007  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, 919-961, (1988) · Zbl 0658.05006  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, 181-188, (1990) · Zbl 0717.05004  Stanley, R. P., Problem 90-2, Mathem. Intelligencer, 12, 65, (1990)  Stanton, D. and White, D., Constructive Combinatorics, Springer-Verlag, 1986. · Zbl 0595.05002  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.
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.