The number of extreme points of tropical polyhedra

Details The number of extreme points of tropical polyhedra The number of extreme points of tropical polyhedra

2009-06-18

arxiv.org/abs/0906.3492v1

Journal of Combinatorial Theory, Series A, Volume 118, Issue 1, January 2011, Pages 162-189

Mathematics

Combinatorics

26 pages, 4 figures, 1 table

Scientific paper

10.1016/j.jcta.2010.04.003

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.

Affiliated with

Also associated with

No associations

Rating

The number of extreme points of tropical polyhedra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The number of extreme points of tropical polyhedra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The number of extreme points of tropical polyhedra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-725864