English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

A polytopal digraph $G(P)$ is an orientation of the skeleton of a convexpolytope $P$. The possible non-degenerate pivot operations of the simplexmethod in solving a linear program over $P$ can be represented as a specialpolytopal digraph known as an LP digraph. Presently there is no generalcharacterization of which polytopal digraphs are LP digraphs, although fournecessary properties are known: acyclicity, unique sink orientation(USO), theHolt-Klee property and the shelling property. The shelling property wasintroduced by Avis and Moriyama (2009), where two examples are given in $d=4$dimensions of polytopal digraphs satisfying the first three properties but notthe 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 anacyclic USO that satisfies the Holt-Klee property, but does not satisfy theshelling property. The construction was based on a minimal such example, whichhas $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, whichwe then prove is equivalent to the original definition. Using this strongercondition we are able to give a more general construction of such families. Inparticular, 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 completecharacterization of LP orientations.

Families of polytopal digraphs that do not satisfy the shelling property