## A greedoid polynomial which distinguishes rooted arborescences

HTML articles powered by AMS MathViewer

- by Gary Gordon and Elizabeth McMahon PDF
- Proc. Amer. Math. Soc.
**107**(1989), 287-298 Request permission

## 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.## References

- Anders Björner, Bernhard Korte, and László Lovász,
*Homotopy properties of greedoids*, Adv. in Appl. Math.**6**(1985), no. 4, 447–494. MR**826593**, DOI 10.1016/0196-8858(85)90021-1 - Anders Björner and Günter M. Ziegler,
*Introduction to greedoids*, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 284–357. MR**1165545**, DOI 10.1017/CBO9780511662041.009 - T. Brylawski and D. Kelly,
*Matroids and combinatorial geometries*, Carolina Lecture Series, University of North Carolina, Department of Mathematics, Chapel Hill, N.C., 1980. MR**573268** - Thomas Brylawski and James Oxley,
*The Tutte polynomial and its applications*, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 123–225. MR**1165543**, DOI 10.1017/CBO9780511662041.007
G. Gordon and L. Traldi, - Bernhard Korte and László Lovász,
*Polymatroid greedoids*, J. Combin. Theory Ser. B**38**(1985), no. 1, 41–72. MR**782625**, DOI 10.1016/0095-8956(85)90091-7
W. Tutte,

*Polynomials for directed graphs*, submitted.

*Graph theory*, Cambridge Univ. Press, Cambridge, 1984. N. White, ed.,

*Matroid Theory*, Cambridge Univ. Press, Cambridge, 1985.

## Additional Information

- © Copyright 1989 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**107**(1989), 287-298 - MSC: Primary 05B35; Secondary 05C20
- DOI: https://doi.org/10.1090/S0002-9939-1989-0967486-0
- MathSciNet review: 967486