论文标题
在多层图上枚举木骨和单调路径的枚举问题
Enumerative problems for arborescences and monotone paths on polytope graphs
论文作者
论文摘要
凸polytope $ p $上的每个通用线性功能$ f $均在$ p $的图上引起方向。从由此产生的有向图中可以定义$ f $ arborescence的概念和$ p $上的$ f $ - 单子路径，以及$ f $ - 单调路径的顶点集合的自然图结构。这些概念在几何组合和优化中很重要。 本文限制了$ f $ -arborescences的数量，$ f $ - 单调路径的数量以及$ f $ - 单调路径的直径，用于$ f $ - 单调路径$ p $在其尺寸和顶点或方面的数量方面。
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.
