Duality of graded graphs (Q1337042): Difference between revisions

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.