A greedoid polynomial which distinguishes rooted arborescences

Abstract:

We define a two-variable polynomial ${f_G}(t,z)$ for a greedoid $G$ which generalizes the standard one-variable greedoid polynomial ${\lambda _G}(t)$. Several greedoid invariants (including the number of feasible sets, bases, and spanning sets) are easily shown to be evaluations of ${f_G}(t,z)$. We prove (Theorem 2.8) that when $G$ is a rooted directed arborescence, ${f_G}(t,z)$ completely determines the arborescence. We also show the polynomial is irreducible over ${\mathbf {Z}}[t,z]$ for arborescences with only one edge directed out of the distinguished vertex. When $G$ is a matroid, ${f_G}(t,z)$ coincides with the Tutte polynomial. We also give an example to show Theorem 2.8 fails for full greedoids. This example also shows ${f_G}(t,z)$ does not distinguish rooted arborescences among the class of all greedoids.