# 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:
 [1] Aigner, M, Combinatorial Theory, Springer-Verlag, 1979. [2] Birkhoff, G., Lattice Theory, 3rd ed., Amer. Math. Soc., Providence, RI, 1967. [3] Björner, A., “The Möbius 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, Zapiski Nauchn. Sem. LOMI, 155, 156-175, (1986) · Zbl 0661.05004 [6] Fomin, S., Duality of graded graphs, Report No. 15 (1991/92), Institut Mittag-Leffler, 1992. · Zbl 0810.05005 [7] 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 [8] 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. [9] Fomin, S. and Stanton, D., Rim hook lattices, Report No. 23 (1991/92), Institut Mittag-Leffler, 1992. · Zbl 0897.05086 [10] Greene, C., An extension of Schensted’s theorem, Adv. in Math., 14, 254-265, (1974) · Zbl 0303.05006 [11] Haiman, M. D., On mixed insertion, symmetry, and shifted Young tableaux, J. Combin. Theory, 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] Macdonald, I.G., Symmetric Functions and Hall Polynomials, Oxford Univ. Press, Oxford, 1979. · Zbl 0487.20007 [14] Propp, J., Some variants of Ferrers diagrams, J. Combin. Theory, 52, 98-128, (1989) · Zbl 0682.05007 [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, 27, 10-18, (1979) · Zbl 0428.05005 [17] Sagan, B. E., Shifted tableaux, Schur $$Q$$-functions and a conjecture of R. Stanley, J. Comb. Theory, 45, 62-103, (1987) · Zbl 0661.05010 [18] Sagan, B.E., “The ubiquitous Young tableaux,” Invariant Theory and Tableaux, D. Stanton, Ed., Springer-Verlag, 1990, 262-298. [19] 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 [20] Schensted, C., Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191, (1961) · Zbl 0097.25202 [21] 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. [22] Stanley, R. P., Theory and application of plane partitions, Studies in Applied Math., 50, 167-188, (1971) · Zbl 0225.05011 [23] Stanley, R.P., “Ordered structures and partitions,” Mem. Amer. Math. Soc.119 (1972). · Zbl 0246.05007 [24] Stanley, R. P., The Fibonacci lattice, Fibonacci Quart., 13, 215-232, (1975) · Zbl 0328.06007 [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, 919-961, (1988) · Zbl 0658.05006 [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, 181-188, (1990) · Zbl 0717.05004 [29] Stanley, R. P., Problem 90-2, Mathem. Intelligencer, 12, 65, (1990) [30] Stanton, D. and White, D., Constructive Combinatorics, Springer-Verlag, 1986. · Zbl 0595.05002 [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.
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.