A bound for the number of vertices of a polytope with applications
A bound for the number of vertices of a polytope with applications
复制标题
具有应用的多胞形顶点数的界限
DOI：
10.1007/s00493-013-2870-9
复制
发表时间：
2011
期刊：
影响因子：
1.1
通讯作者：
A. Barvinok
中科院分区：
文献类型：
--
作者：
A. Barvinok
我们证明了一个特定类型的多面体的顶点数是指数大的维数的多面体。作为推论，我们证明了n维中心对称多面体的顶点数为{ie 1 -1}，且当k≥ 2 r +1且每边至少有两个顶点的割的边数大于k/r时，k-正则图的r-因子数是图的顶点数的指数倍.
We prove that the number of vertices of a polytope of a particular kind is exponentially large in the dimension of the polytope. As a corollary, we prove that an n-dimensional centrally symmetric polytope with O(n) facets has {ie1-1} vertices and that the number of r-factors in a k-regular graph is exponentially large in the number of vertices of the graph provided k≥2r+1 and every cut in the graph with at least two vertices on each side has more than k/r edges.