Descriptions of polyDB Collections

This page describes collections in the polymake Database. The data can be accessed via web interface or from within the polymake system.

Polytropes in the tropical projective 3-torus

A polytrope is a tropical polytope which is convex in the ordinary sense [6]. Since their facet normals (as an ordinary polytope) are vectors in the root system of type A, they are also known as "alcoved polytopes" (of type A) [8]. Polytropes arise as tropical eigenspaces [2] and are closely related to the Kleene stars [11], which occur in combinatorial optimization (e.g., in the Floyd-Warshall algorithm for computing all shortest paths [10]).

The combinatorial study of tropical polytopes was started by Develin and Sturmfels [3]. Joswig and Kulas investigated polytropes as geometric objects in their own right [6]. Lam and Postnikov studied polytropes under the name "alcoved polytopes" [8].

A tropical polytope in the line R2/R1 is an interval and hence a polytrope. Up to combinatorial equivalence there are precisely five distinct types of polytropes in the plane R3/R1. In [6] it was erroneously claimed that there are only five combinatorial types of polytropes in the tropical projective 3-torus R4/R1 with exactly 20 ordinary vertices (the maximum number). This was corrected by Jiménez and de la Puente [4], who found the sixth type and showed that this is the complete list; see also [9]. The full classification of polytropes in the tropical projective 3-torus, not only of the maximal ones, was obtained by Tran [13]; there are 1013 combinatorial types. Here is the detailed statistics per number of ordinary vertices:
4:1 5:1 6:5 7:6 8:34 9:38 10:81 11:101 12:151 13:144 14:154 15:116 16:92 17:46 18:28 19:9 20:6

The collection is based on the data from Tran's classification. For each maximal cone in the fan computed there (and described in [13]) we determine the barycenter of the rays (scaled to coprime integer coordinates) as a representative. These yield lifting functions for certain regular subdivisions of Δ33.

[1] Marianne Akian, Stéphane Gaubert, and Andrea Marchesini. Tropical bounds for eigenvalues of matrices. Linear Algebra and its Applications, 446:281--303, 2014. [ bib | DOI | arXiv ]
[2] Peter Butkovič. Max-linear systems: theory and algorithms. Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London, 2010. [ bib | DOI | http ]
[3] Mike Develin and Bernd Sturmfels. Tropical convexity. Doc. Math., 9:1--27 (electronic), 2004. correction: ibid., pp. 205--206. [ bib ]
[4] Adrián Jiménez and María Jesús de la Puente. Six combinatorial clases of maximal convex tropical polyhedra, 2012. [ bib | arXiv ]
[5] Marianne Johnson and Mark Kambites. Convexity of tropical polytopes. Linear Algebra Appl., 485:531--544, 2015. [ bib | DOI | http ]
[6] Michael Joswig and Katja Kulas. Tropical and ordinary convexity combined. Adv. Geometry, 10:333--352, 2010. [ bib ]
[7] Michael Joswig and Georg Loho. Weighted digraphs and tropical cones. Linear Algebra Appl., 501:304--343, 2016. [ bib | DOI ]
[8] Thomas Lam and Alexander Postnikov. Alcoved polytopes. I. Discrete Comput. Geom., 38(3):453--478, 2007. [ bib ]
[9] María Jesús de la Puente. On tropical Kleene star matrices and alcoved polytopes. Kybernetika (Prague), 49(6):897--910, 2013. [ bib ]
[10] Alexander Schrijver. Combinatorial optimization. Polyhedra and efficiency. Vol. A, volume 24 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2003. Paths, flows, matchings, Chapters 1--38. [ bib ]
[11] SergeĬ Sergeev. Max-plus definite matrix closures and their eigenspaces. Linear Algebra Appl., 421(2-3):182--201, 2007. [ bib | DOI | http ]
[12] Bernd Sturmfels and Ngoc Mai Tran. Combinatorial types of tropical eigenvectors. Bull. Lond. Math. Soc., 45(1):27--36, 2013. [ bib | DOI | http ]
[13] Ngoc Mai Tran. Enumerating polytropes, 2013. [ bib | arXiv ]

Last modified: Die Dez 20:32:31 UTC 2016 by mic