The number of extreme points of tropical polyhedra

DOI10.1016/J.JCTA.2010.04.003zbMATH Open1246.14078arXiv0906.3492OpenAlexW2082820693MaRDI QIDQ616447FDOQ616447

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)

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.

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

Recommendations

• On the Monotone Upper Bound Problem
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The tropical analogue of polar cones
• Long monotone paths on simple 4-polytopes
• Combinatorics of tropical polytopes
• ``Even more intriguing, if rather less plausible\dots Face numbers of convex polytopes
• Minimal external representations of tropical polyhedra
• scientific article; zbMATH DE number 609981
• Tropical convexity
• On the dimension of max-min convex sets

zbMATH Keywords

extreme pointslattice pathstropical convexitycyclic polytopeupper bound theoremmax-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)

Cites Work

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

Cited In (16)

• Tropical polar cones, hypergraph transversals, and mean payoff games
• Tropical linear-fractional programming and parametric mean payoff games
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• An interval version of separation by semispaces in max-min convexity
• The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems
• Minimal half-spaces and external representation of tropical polyhedra
• Monomial Tropical Cones for Multicriteria Optimization
• Complete solution of tropical vector inequalities using matrix sparsification.
• Computing the vertices of tropical polyhedra using directed hypergraphs
• Enumerating extreme points of a highly degenerate polytope
• Tropical Gaussians: a brief survey
• Tropical polyhedra are equivalent to mean payoff games
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• Minimal external representations of tropical polyhedra
• Tropicalizing the Simplex Algorithm
• On max-plus two-sided linear systems whose solution sets are min-plus linear

Uses Software

• TPLib

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616447)