2020/02/03 by Athanasiadis, Christos, De Loera, Jesús, Zhang, Zhenyang
#05C20 #05C30 #05C35 #52B12 #52B55 #90C05 #90C08 #Combinatorics (math.CO) #F.2.2 #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2002.00999
Every generic linear functional f on a convex polytope P induces an orientation on the graph of P. From the resulting directed graph one can define a notion of f-arborescence and f-monotone path on P, as well as a natural graph structure on the vertex set of f-monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of f-arborescences, the number of f-monotone paths, and the diameter of the graph of f-monotone paths for polytopes P in terms of their dimension and number of vertices or facets.