Minimal external representations of tropical polyhedra

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 Rn (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".Fil: Allamigeon, Xavier. Institut National de Recherche en Informatique et en Automatique; Francia. Ecole Polytechnique. Centre de Mathématiques Appliquées; FranciaFil: Katz, Ricardo David. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Instituto de Matemática "Beppo Levi"; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Cientifico Tecnológico Rosario; Argentin