Families of polytopal digraphs that do not satisfy the shelling property

Details Families of polytopal digraphs that do not satisfy the shelling property Families of polytopal digraphs that do not satisfy the shelling property

2011-10-13

arxiv.org/abs/1110.3078v1

Computer Science

Discrete Mathematics

Scientific paper

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 \ge 4$ and $n \ge 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 $n_0$ vertices whose unique sink is simple, we can extend $P$ for any $d \ge 4$ and $n \ge n_0 + 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.

Affiliated with

Also associated with

No associations

Rating

Families of polytopal digraphs that do not satisfy the shelling property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Families of polytopal digraphs that do not satisfy the shelling property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Families of polytopal digraphs that do not satisfy the shelling property will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521840