Groupe d’études et de recherche en analyse des décisions

G-2008-08

On Combinatorial Properties of Linear Program Digraphs

et

An LP-digraph is a directed graph which consists of the vertices and edges of a polytope P directed by a linear function in general position. It is known that an LP-digraph satisfies three necessary conditions: it is acyclic, each face of P has a unique sink (USO), and the Holt-Klee condition holds. These three conditions are not sufficient in general for a directed graph on P to be an LP-digraph. In this paper we survey the relationships between these three condtions and introduce a new necessary condition, the shelling condition. We show that the shelling condition is stronger than a combination of the acyclicity and Holt-Klee conditions for polytopes in dimension at least 4 which are non-simple. In all other cases, we show that it is equivalent to the intersection of these two conditions.

, 16 pages