The number of extreme points of tropical polyhedra

Abstract

The celebrated upper bound theorem of McMullen determines the maximal number of extreme points of a polyhedron in terms of its dimension and the number of constraints which define it, showing that the maximum is attained by the polar of the cyclic polytope. We show that the same bound is valid in the tropical setting, up to a trivial modification. Then, we study the natural candidates to be the maximizing polyhedra, which are the polars of a family of cyclic polytopes equipped with a sign pattern. We construct bijections between the extreme points of these polars and lattice paths depending on the sign pattern, from which we deduce explicit bounds for the number of extreme points, showing in particular that the upper bound is asymptotically tight as the dimension tends to infinity, keeping the number of constraints fixed. When transposed to the classical case, the previous constructions yield some lattice path generalizations of Gale's evenness criterion.

26 pages, 4 figures, 1 table

References in corpus (10)

• Duality and separation theorems in idempotent semimodules
• Enumerative tropical algebraic geometry in R2
• 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
• The tropical analogue of polar cones
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The tropical double description method
• Cyclic projectors and separation theorems in idempotent convex geometry
• Carathéodory, Helly and the others in the max-plus world

Cited by in corpus (15)

• Tropical polyhedra are equivalent to mean payoff games
• Tropicalizing the simplex algorithm
• Computing the vertices of tropical polyhedra using directed hypergraphs
• Tropical linear-fractional programming and parametric mean payoff games
• Minimal half-spaces and external representation of tropical polyhedra
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Combinatorial simplex algorithms can solve mean payoff games
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Minimal external representations of tropical polyhedra
• Six combinatorial clases of maximal convex tropical polyhedra
• On $2\times 2$ Tropical Commuting Matrices
• Tropical Gaussians: A Brief Survey
• An interval version of separation by semispaces in max-min convexity
• On max-plus two-sided linear systems whose solution sets are min-plus linear
• The Nullstellensatz and Positivstellensatz for Sparse Tropical Polynomial Systems