Leírás
EGERVÁRY SZEMINÁRIUM
Abstract: It is well-known that for a connected Eulerian digraph, the number of arborescences rooted at a vertex r is independent of the choice of r. This statement has a generalization, which is the following: The branching greedoid of a rooted digraph is a set system (slightly similar to matroids) where the bases are the spanning arborescences. The greedoid polynomial is the generating function of certain activities for the spanning arborescences. It was proved by Chan, that for Eulerian digraphs, not only the number of spanning arborescences, but also the greedoid polynomial is independent of the choice of root vertex. We give a new, geometric proof for this statement. Take an arbitrary totally unimodular matrix representing the (oriented) cographic matroid of D. It turns out that the greedoid polynomial is the Ehrhart h*-polynomial of this polytope (that is defined using integer point counts), hence we get a definition that does not use any root vertex. The proof is based on the fact that spanning arborescences yield a triangulation for the polytope. As a byproduct we also obtain some bizarre alternative definitions for the greedoid polynomial of Eulerian branching greedoids.
It is unclear if there is any similar geometric definition for the greedoid polynomial of non-Eulerian branching greedoids.