This page describes collections in the polymake Database. The data can be accessed via web interface or from within the polymake system.
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 Δ3xΔ3.
[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: Son Sep 09:08:56 UTC 2019 by mic