Duality of graded graphs (Q1337042): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Fomin, Sergey / rank | |||
Property / reviewed by | |||
Property / reviewed by: Nikolai I. Osetinski / rank | |||
Property / author | |||
Property / author: Fomin, Sergey / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Nikolai I. Osetinski / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3050437 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5331549 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3487448 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3809803 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Duality of graded graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Schensted algorithms for dual graded graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4396992 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An extension of Schensted's theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On mixed insertion, symmetry, and shifted Young tableaux / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Permutations, matrices, and generalized Young tableaux / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3947818 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some variants of Ferrers diagrams / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An analog of Schensted's algorithm for shifted Young tableaux / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Shifted tableaux, Schur q-functions, and a conjecture of R. Stanley / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3356338 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Longest Increasing and Decreasing Subsequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Theory and Application of Plane Partitions: Part 1 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ordered structures and partitions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4093495 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3748279 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Differential Posets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3487399 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Further combinatorial properties of two Fibonacci lattices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3726126 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4039860 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:01, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Duality of graded graphs |
scientific article |
Statements
Duality of graded graphs (English)
0 references
2 April 1995
0 references
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.
0 references
tableaux
0 references
differential poset
0 references
Young diagram
0 references
graded graph
0 references
combinatorial identities
0 references
enumerative functions
0 references
Young-Frobenius identity
0 references
enumerative identities
0 references