The number of extreme points of tropical polyhedra (Q616447)

\textit{P. McMullen}'s upper bound theorem [Mathematika, Lond. 17, 179--184 (1970; Zbl 0217.46703)], one of the most important theorems in the theory of convex polytopes, states that the maximum number of faces, in each dimension, of a \(d\)-polytope with \(p\) extreme points (vertices) is attained by the cyclic polytope or, in the dual form, the polar of a cyclic polytope with \(p\) extreme points maximizes the number of extreme points among all polytopes of dimension \(d\) defined by \(p\) inequalities. The number of codimension-one faces is bounded above by a known function \(U(p,d)\). The paper under review is devoted to max-plus or tropical convexity---an area of great current vitality. There are two main results in the paper. The first result shows that a McMullen type bound is valid in the tropical setting and is translated into the tropical language as follows: The number of extreme rays (which correspond to extreme points in the classical setting) in a tropical cone (which correspond to a polytope) defined by \(p\) linear tropical inequalities in \((\mathbb{R} \cup \{-\infty\})^d\) is bounded above by \(U(p + d, d -1)\). The notion of tropical polar was introduced by \textit{S. Gaubert} and \textit{R. D. Katz} [Linear Algebra Appl. 431, No.~5--7, 608--625 (2009; Zbl 1172.52002)], which enables the authors to define a family of tropical generalizations of cyclic polytopes. The second result of the paper says that the extreme rays of the polar of a signed cyclic polyhedral cone are in one-to-one correspondence with certain lattice paths depending on the sign pattern. From this, the authors derive explicit bounds on the number of extreme points.