Minimal external representations of tropical polyhedra

Abstract

Tropical polyhedra are known to be representable externally, as intersections of finitely many tropical half-spaces. However, unlike in the classical case, the extreme rays of their polar cones provide external representations containing in general superfluous half-spaces. In this paper, we prove that any tropical polyhedral cone in R^n (also known as "tropical polytope" in the literature) admits an essentially unique minimal external representation. The result is obtained by establishing a (partial) anti-exchange property of half-spaces. Moreover, we show that the apices of the half-spaces appearing in such non-redundant external representations are vertices of the cell complex associated with the polyhedral cone. We also establish a necessary condition for a vertex of this cell complex to be the apex of a non-redundant half-space. It is shown that this condition is sufficient for a dense class of polyhedral cones having "generic extremities".

v1: 32 pages, 10 figures; v2: minor revision, 34 pages, 10 figures

References in corpus (9)

• Duality and separation theorems in idempotent semimodules
• The Minkowski Theorem for Max-plus Convex Sets
• Computing the vertices of tropical polyhedra using directed hypergraphs
• Minimal half-spaces and external representation of tropical polyhedra
• Idempotent functional analysis: an algebraic approach
• The number of extreme points of tropical polyhedra
• The tropical analogue of polar cones
• The tropical double description method
• Tropical polar cones, hypergraph transversals, and mean payoff games

Cited by in corpus (5)

• Tropicalizing the simplex algorithm
• Using Dynamic Analysis to Generate Disjunctive Invariants
• Conditional Independence in Max-linear Bayesian Networks
• Approximating the Volume of Tropical Polytopes is Difficult
• Face posets of tropical polyhedra and monomial ideals