Families of polytopal digraphs that do not satisfy the shelling property
Families of polytopal digraphs that do not satisfy the shelling property
复制标题
不满足脱壳性质的多面有向图家族
DOI：
10.1016/j.comgeo.2012.10.005
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Sonoko Moriyama
中科院分区：
文献类型：
--
作者：
David Avis;Hiroyuki Miyata;Sonoko Moriyama
一个多面体有向图G（P）是凸多面体P的骨架的一个定向。单纯形法在求解P上的线性规划时可能的非退化主元运算可以表示为一个特殊的多面体有向图，称为LP有向图。目前还没有一般性的刻画，哪些多面体有向图是LP有向图，虽然四个必要的性质是已知的：无环性，唯一的汇方向（USO），霍尔特-克利性质和脱壳性质。Avis和Moriyama（2009）引入了脱壳性质，其中给出了d=4维的多面体有向图满足前三个性质但不满足脱壳性质的两个例子。这些例子中较小的一个有n=7个顶点。Avis，Miyata and Moriyama（2009）对每个d ≠ 4和n ≠ d+2构造了一个n阶d-多胞形P，它的一个多面体有向图是一个无圈USO，满足Holt-Klee性质，但不满足shelling性质。该构造基于最小的这样的示例，其具有d=4和n=6。本文对脱壳条件作了进一步的探讨。首先，我们给出了一个明显更强的定义的脱壳性能，然后我们证明是等价于原来的定义。利用这个更强的条件，我们能够给出这类族的更一般的构造。特别地，我们证明了给定任何n阶的四维多面体P，其唯一汇是单的，我们可以将P对任何d <$4和n <$n0 +d−4扩展到具有这些性质的n阶d-多面体。最后，我们研究了d-crosspolytopes的壳条件的强度，对于这一点，Reynin（2004）给出了LP取向的完整表征。
A polytopal digraph G(P) is an orientation of the skeleton of a convex polytope P. The possible non-degenerate pivot operations of the simplex method in solving a linear program over P can be represented as a special polytopal digraph known as an LP digraph. Presently there is no general characterization of which polytopal digraphs are LP digraphs, although four necessary properties are known: acyclicity, unique sink orientation (USO), the Holt–Klee property and the shelling property. The shelling property was introduced by Avis and Moriyama (2009), where two examples are given in d=4 dimensions of polytopal digraphs satisfying the first three properties but not the shelling property. The smaller of these examples has n=7 vertices. Avis, Miyata and Moriyama (2009) constructed for each d⩾4 and n⩾d+2, a d-polytope P with n vertices which has a polytopal digraph which is an acyclic USO that satisfies the Holt–Klee property, but does not satisfy the shelling property. The construction was based on a minimal such example, which has d=4 and n=6. In this paper we explore the shelling condition further. First we give an apparently stronger definition of the shelling property, which we then prove is equivalent to the original definition. Using this stronger condition we are able to give a more general construction of such families. In particular, we show that given any 4-dimensional polytope P with n0vertices whose unique sink is simple, we can extend P for any d⩾4 and n⩾n0+d−4 to a d-polytope with these properties that has n vertices. Finally we investigate the strength of the shelling condition for d-crosspolytopes, for which Develin (2004) has given a complete characterization of LP orientations.