Enumerative problems for arborescences and monotone paths on polytope graphs
Abstract
Every generic linear functional (Formula presented.) on a convex polytope (Formula presented.) induces an orientation on the graph of (Formula presented.). From the resulting directed graph one can define a notion of (Formula presented.) -arborescence and (Formula presented.) -monotone path on (Formula presented.), as well as a natural graph structure on the vertex set of (Formula presented.) -monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of (Formula presented.) -arborescences, the number of (Formula presented.) -monotone paths, and the diameter of the graph of (Formula presented.) -monotone paths for polytopes (Formula presented.) in terms of their dimension and number of vertices or facets.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.