Duality of graded graphs
type: Item
instance of: scholarly article
title: Duality of graded graphs
zbMATH Open document ID: 0810.05005
DOI: 10.1023/A:1022412010826
published in: Journal of Algebraic Combinatorics
publication date: 1995-04-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A19
Mathematics Subject Classification ID: 05E10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 06D99
zbMATH DE Number: 672157
zbMATH Keywords: tableaux
zbMATH Keywords: differential poset
zbMATH Keywords: Young diagram
zbMATH Keywords: graded graph
zbMATH Keywords: combinatorial identities
zbMATH Keywords: enumerative functions
zbMATH Keywords: Young-Frobenius identity
zbMATH Keywords: enumerative identities
author: Sergey Fomin
reviewed by: Nikolai I. Osetinski
MaRDI profile type: Publication
cites work: Q3050437
cites work: Q5331549
cites work: Q3487448
cites work: Q3809803
cites work: Schensted algorithms for dual graded graphs
cites work: Q4396992
cites work: An extension of Schensted's theorem
cites work: On mixed insertion, symmetry, and shifted Young tableaux
cites work: Permutations, matrices, and generalized Young tableaux
cites work: Q3947818
cites work: Some variants of Ferrers diagrams
cites work: An analog of Schensted's algorithm for shifted Young tableaux
cites work: Shifted tableaux, Schur q-functions, and a conjecture of R. Stanley
cites work: Q3356338
cites work: Longest Increasing and Decreasing Subsequences
cites work: Theory and Application of Plane Partitions: Part 1
cites work: Ordered structures and partitions
cites work: Q4093495
cites work: Q3748279
cites work: Differential Posets
cites work: Q3487399
cites work: Further combinatorial properties of two Fibonacci lattices
cites work: Q3726126
cites work: Q4039860
full work available at URL: a:1022412010826
OpenAlex ID: W166248731
description: scientific article; zbMATH DE number 672157