|
The interior polynomial of a directed graph is defined as the $h^*$-polynomial of the graph's (extended) root polytope, and it displays several attractive properties. Here we express its degree in terms of the minimum cardinality of a directed join. We present a natural generalization of this result to oriented regular matroids; in the process we also give a facet description for the extended root polytope of a regular oriented matroid.
By duality, our expression for the degree of the interior polynomial implies a formula for the degree of the parking function enumerator of an Eulerian directed graph (which is equivalent to the greedoid polynomial of the corresponding branching greedoid). We extend that result further to obtain the degree of the parking function enumerator of an arbitrary rooted directed graph in terms of the minimum cardinality of a certain type of feedback arc set.
Bibtex entry:
| AUTHOR | = | {K{\'a}lm{\'a}n, Tam{\'a}s and T{\'o}thm{\'e}r{\'e}sz, Lilla}, |
| TITLE | = | {Degrees of interior polynomials and parking function enumerators}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2023}, |
| NUMBER | = | {TR-2023-03} |