Minimal half-spaces and external representation of tropical polyhedra Export

@article{citeulike:5432822, abstract = {We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which appeared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski-Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.}, archivePrefix = {arXiv}, author = {Gaubert, Stephane and Katz, Ricardo D.}, citeulike-article-id = {5432822}, citeulike-linkout-0 = {http://arxiv.org/abs/0908.1586}, citeulike-linkout-1 = {http://arxiv.org/pdf/0908.1586}, day = {12}, eprint = {0908.1586}, keywords = {tropical}, month = {Aug}, posted-at = {2009-08-13 17:22:39}, priority = {2}, title = {Minimal half-spaces and external representation of tropical polyhedra}, url = {http://arxiv.org/abs/0908.1586}, year = {2009} }

TY - JOUR ID - citeulike:5432822 L3 - citeulike-article-id:5432822 N2 - We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which appeared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski-Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors. TI - Minimal half-spaces and external representation of tropical polyhedra KW - tropical AU - Gaubert, Stephane AU - Katz, Ricardo PY - 2009/Aug/12/ UR - http://arxiv.org/abs/0908.1586 ER -