Duality of graded graphs

Combinatorial identities, bijective combinatorics (05A19) Trees (05C05) Combinatorial aspects of representation theory (05E10) Combinatorics of partially ordered sets (06A07) Distributive lattices (06D99) Combinatorial probability (60C05)

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.

Recommendations

Cites work

Cited in

(55)

This page was built for publication: Duality of graded graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337042)