The number of extreme points of tropical polyhedra

DOI10.1016/j.jcta.2010.04.003zbMath1246.14078arXiv0906.3492OpenAlexW2082820693MaRDI QIDQ616447

Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz

Publication date: 7 January 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0906.3492

zbMATH Keywords

extreme pointslattice pathsupper bound theoremtropical convexitycyclic polytopemax-plus convexityGale's evenness condition

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Axiomatic and generalized convexity (52A01)

Related Items (max. 100)

TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES ⋮ Tropicalizing the Simplex Algorithm ⋮ Tropical Fourier–Motzkin elimination, with an application to real-time verification ⋮ Tropical Gaussians: a brief survey ⋮ The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems ⋮ Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria ⋮ Computing the vertices of tropical polyhedra using directed hypergraphs ⋮ Monomial Tropical Cones for Multicriteria Optimization ⋮ Minimal half-spaces and external representation of tropical polyhedra ⋮ Tropical linear-fractional programming and parametric mean payoff games ⋮ Complete solution of tropical vector inequalities using matrix sparsification. ⋮ Tropical polar cones, hypergraph transversals, and mean payoff games ⋮ An interval version of separation by semispaces in max-min convexity

Uses Software

• TPLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The Minkowski theorem for max-plus convex sets
• Generators, extremals and bases of max cones
• The tropical analogue of polar cones
• Moduloïds and pseudomodules. I: Dimension theory
• Shelling polyhedral 3-balls and 4-polytopes
• Duality and separation theorems in idempotent semimodules.
• Tropical convexity
• Carathéodory, Helly and the others in the max-plus world
• Tropical convexity via cellular resolutions
• Linear independence over tropical semirings and beyond
• Inferring Min and Max Invariants Using Max-Plus Polyhedra
• The Tropical Rank of a Tropical Matrix
• Enumerative tropical algebraic geometry in ℝ²
• -convexity
• Methods and applications of (max,+) linear algebra
• Max-Plus $(A,B)$-Invariant Spaces and Control of Timed Discrete-Event Systems
• Affine Buildings and Tropical Convexity
• Tropical Polytopes and Cellular Resolutions
• Max-Plus Convex Geometry
• The maximum numbers of faces of a convex polytope
• Max-plus convex sets and max-plus semispaces. I
• Idempotent functional analysis: An algebraic approach

This page was built for publication: The number of extreme points of tropical polyhedra