Paths along graded posets

222 Views Asked by At

I'm wondering whether or not there are any resources available which deal with the number of distinct paths along a graded poset. I am relatively new to this area so I don't know if this is an interesting question to ask in the first place. But I've found some fairly interesting sequences from counting these paths on various posets, so I was curious as to whether this has been studied.

Edit: Here is an example: https://oeis.org/A002846.

1

There are 1 best solutions below

0
On

The topic comes up in Richard Stanley's Enumerative Combinatorics Volume 1, chapter 3. Edition 2 is freely available: http://math.mit.edu/~rstan/ec/ec1.pdf

Regarding examples, there are many. Consider the poset of an $(n+1)$-by-$(k+1)$ grid ordered by $(x,y) \leq (x',y') \iff x \leq x' \text{ and } y \leq y'$ graded by $\rho(x,y) = x + y$. The number of paths from $(0,0)$ to $(n,k)$ is $\binom{n+k}{k}$.

For an $(n+1)$-by-$(n+1)$ grid without points below the diagonal, using the same order and grading as in the previous example, the number of paths from $(0,0)$ to $(n,n)$ is the $n$-th Catalan number.

The number of paths from bottom to top in the Boolean lattice is $n!$.

For general facts, there are some nice theorems. For example, a distributive lattice and the poset of antichains in such a lattice are closely related. The number of maximal chains (ie paths) in a distributive lattice is the same as the number of linear extensions of the poset of antichains.

For a graded poset with unique top and bottom element, let $f(v)$ be the number of maximal chains from the bottom to vertex $v$. If $w_1,\ldots,w_k$ are predecessors of $v$, then $f(v) = f(w_1) + \cdots + f(w_k)$. Thus, even when there isn't a nice formula, the number of maximal chains in such a graded poset can be counted recursively.