AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Essentials of Tropical Combinatorics
About this Title
Michael Joswig, Max-Planck Institut für Mathematik in den Naturwissenschaften, Leipzig, Germany
Publication: Graduate Studies in Mathematics
Publication Year:
2021; Volume 219
ISBNs: 978-1-4704-6653-4 (print); 978-1-4704-6740-1 (online)
DOI: https://doi.org/10.1090/gsm/219
Table of Contents
Download chapters as PDF
Front/Back Matter
Chapters
- Tropical hypersurfaces
- Fields of power series and tropicalization
- Graph algorithms and polyhedra
- Products of tropical polynomials and the Cayley trick
- Tropical convexity
- Combinatorics of tropical polytopes
- Tropical half-spaces
- Tropical linear programming
- Feasibility and mean payoffs
- Matroids and tropical linear spaces
- Geometric combinatorics
- Computational complexity
- Using $\texttt {polymake}$
- Hints to selected problems
- Federico Ardila and Sara Billey, Flag arrangements and triangulations of products of simplices, Adv. Math. 214 (2007), no. 2, 495–524. MR 2349710, DOI 10.1016/j.aim.2007.02.014
- Peter Abramenko and Kenneth S. Brown, Buildings, Graduate Texts in Mathematics, vol. 248, Springer, New York, 2008. Theory and applications. MR 2439729, DOI 10.1007/978-0-387-78835-7
- John W. Anthony, Richard A. Bideaux, Kenneth W. Bladh, and Monte C. Nichols, Handbook of mineralogy, vol. II, Mineral Data Publishing, 2003, reprinted version.
- Leslie Hogben (ed.), Handbook of linear algebra, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2014. MR 3013937
- Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig, Combinatorial simplex algorithms can solve mean payoff games, SIAM J. Optim. 24 (2014), no. 4, 2096–2117. MR 3504692, DOI 10.1137/140953800
- Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig, Tropicalizing the simplex algorithm, SIAM J. Discrete Math. 29 (2015), no. 2, 751–795. MR 3336300, DOI 10.1137/130936464
- Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig, Log-barrier interior point methods are not strongly polynomial, SIAM J. Appl. Algebra Geom. 2 (2018), no. 1, 140–178. MR 3772004, DOI 10.1137/17M1142132
- Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig, What tropical geometry tells us about the complexity of linear programming, SIAM Rev. 63 (2021), no. 1, 123–164. MR 4209657, DOI 10.1137/20M1380211
- Shreeram S. Abhyankar, Algebraic geometry for scientists and engineers, Mathematical Surveys and Monographs, vol. 35, American Mathematical Society, Providence, RI, 1990. MR 1075991, DOI 10.1090/surv/035
- David Avis, David Bremner, and Raimund Seidel, How good are convex hull algorithms?, Comput. Geom. 7 (1997), no. 5-6, 265–301. 11th ACM Symposium on Computational Geometry (Vancouver, BC, 1995). MR 1447243, DOI 10.1016/S0925-7721(96)00023-5
- Dan Abramovich, Lucia Caporaso, and Sam Payne, The tropicalization of the moduli space of curves, Ann. Sci. Éc. Norm. Supér. (4) 48 (2015), no. 4, 765–809 (English, with English and French summaries). MR 3377065, DOI 10.24033/asens.2258
- Federico Ardila and Mike Develin, Tropical hyperplane arrangements and oriented matroids, Math. Z. 262 (2009), no. 4, 795–816. MR 2511751, DOI 10.1007/s00209-008-0400-z
- Xavier Allamigeon, Stéphane Gaubert, and Éric Goubault, The tropical double description method, STACS 2010: 27th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 5, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2010, pp. 47–58. MR 2853909
- Marianne Akian, Stéphane Gaubert, and Alexander Guterman, Tropical polyhedra are equivalent to mean payoff games, Internat. J. Algebra Comput. 22 (2012), no. 1, 1250001, 43. MR 2900854, DOI 10.1142/S0218196711006674
- Xavier Allamigeon, Stéphane Gaubert, and Éric Goubault, Computing the vertices of tropical polyhedra using directed hypergraphs, Discrete Comput. Geom. 49 (2013), no. 2, 247–279. MR 3017909, DOI 10.1007/s00454-012-9469-6
- Assalé Adjé, Stéphane Gaubert, and Eric Goubault, Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs, J. Math. Anal. Appl. 410 (2014), no. 1, 227–240. MR 3109834, DOI 10.1016/j.jmaa.2013.07.076
- Marianne Akian, Stéphane Gaubert, and Alexander Guterman, Tropical Cramer determinants revisited, Tropical and idempotent mathematics and applications, Contemp. Math., vol. 616, Amer. Math. Soc., Providence, RI, 2014, pp. 1–45. MR 3221324, DOI 10.1090/conm/616/12324
- Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz, and Thomas Rehn, Computing convex hulls and counting integer points with polymake, Math. Program. Comput. 9 (2017), no. 1, 1–38. MR 3613012, DOI 10.1007/s12532-016-0104-z
- Xavier Allamigeon, Stéphane Gaubert, and Ricardo D. Katz, The number of extreme points of tropical polyhedra, J. Combin. Theory Ser. A 118 (2011), no. 1, 162–189. MR 2737191, DOI 10.1016/j.jcta.2010.04.003
- Xavier Allamigeon, Stéphane Gaubert, and Ricardo D. Katz, Tropical polar cones, hypergraph transversals, and mean payoff games, Linear Algebra Appl. 435 (2011), no. 7, 1549–1574. MR 2810655, DOI 10.1016/j.laa.2011.02.004
- Marianne Akian, Stéphane Gaubert, Viorel Niţică, and Ivan Singer, Best approximation in max-plus semimodules, Linear Algebra Appl. 435 (2011), no. 12, 3261–3296. MR 2831610, DOI 10.1016/j.laa.2011.06.009
- Xavier Allamigeon, Stéphane Gaubert, and Mateusz Skomra, Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, J. Symbolic Comput. 85 (2018), 25–54. MR 3707850, DOI 10.1016/j.jsc.2017.07.002
- Xavier Allamigeon, Stéphane Gaubert, and Mateusz Skomra, Tropical spectrahedra, Discrete Comput. Geom. 63 (2020), no. 3, 507–548. MR 4074332, DOI 10.1007/s00454-020-00176-1
- Fuensanta Aroca, Cristhian Garay, and Zeinab Toghani, The fundamental theorem of tropical differential algebraic geometry, Pacific J. Math. 283 (2016), no. 2, 257–270. MR 3519102, DOI 10.2140/pjm.2016.283.257
- Nima Arkani-Hamed, Thomas Lam, and Marcus Spradlin, Positive configuration space, Comm. Math. Phys. 384 (2021), no. 2, 909–954. MR 4259378, DOI 10.1007/s00220-021-04041-x
- Federico Ardila and Caroline J. Klivans, The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B 96 (2006), no. 1, 38–49. MR 2185977, DOI 10.1016/j.jctb.2005.06.004
- Xavier Allamigeon and Ricardo D. Katz, Tropicalization of facets of polytopes, Linear Algebra Appl. 523 (2017), 79–101. MR 3624667, DOI 10.1016/j.laa.2017.02.011
- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, Errata: PRIMES is in P [ MR2123939], Ann. of Math. (2) 189 (2019), no. 1, 317–318. MR 3898710, DOI 10.4007/annals.2019.189.1.6
- Daniele Alessandrini, Logarithmic limit sets of real semi-algebraic sets, Adv. Geom. 13 (2013), no. 1, 155–190. MR 3011539, DOI 10.1515/advgeom-2012-0020
- Federico Ardila, Subdominant matroid ultrametrics, Ann. Comb. 8 (2004), no. 4, 379–389. MR 2112691, DOI 10.1007/s00026-004-0227-1
- Federico Ardila, Victor Reiner, and Lauren Williams, Bergman complexes, Coxeter arrangements, and graph associahedra, Sém. Lothar. Combin. 54A (2005/07), Art. B54Aj, 25. MR 2317682
- Josh Alman and Virginia Vassilevska Williams, A refined laser method and faster matrix multiplication, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, pp. 522–539.
- Nina Amenta and Günter M. Ziegler, Deformed products and maximal shadows of polytopes, Advances in discrete and computational geometry (South Hadley, MA, 1996) Contemp. Math., vol. 223, Amer. Math. Soc., Providence, RI, 1999, pp. 57–90. MR 1661377, DOI 10.1090/conm/223/03132
- Martin Aigner and Günter M. Ziegler, Proofs from The Book, 6th ed., Springer, Berlin, 2018. See corrected reprint of the 1998 original [ MR1723092]; Including illustrations by Karl H. Hofmann. MR 3823190, DOI 10.1007/978-3-662-57265-8
- P. Butkovic and A. Aminu, Introduction to max-linear programming, IMA J. Manag. Math. 20 (2009), no. 3, 233–249. MR 2511497, DOI 10.1093/imaman/dpn029
- Matthew Baker and Nathan Bowler, Matroids over partial hyperstructures, Adv. Math. 343 (2019), 821–863. MR 3891757, DOI 10.1016/j.aim.2018.12.004
- Dominik Bendle, Janko Boehm, Yue Ren, and Benjamin Schröter, Parallel computation of tropical varieties, their positive part, and tropical Grassmannians, 2020, Preprint arXiv:2003.13752.
- François Louis Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat, Synchronization and linearity, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1992. An algebra for discrete event systems. MR 1204266
- Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509, DOI 10.1007/978-3-662-03718-8
- Hans-Jürgen Bandelt and Andreas Dress, Reconstructing the shape of a tree from observed dissimilarity data, Adv. in Appl. Math. 7 (1986), no. 3, 309–343. MR 858908, DOI 10.1016/0196-8858(86)90038-2
- Rainer Burkard, Mauro Dell’Amico, and Silvano Martello, Assignment problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. MR 2488749, DOI 10.1137/1.9780898717754
- Richard Bellman, On a routing problem, Quart. Appl. Math. 16 (1958), 87–90. MR 102435, DOI 10.1090/S0033-569X-1958-0102435-2
- Pascal Benchimol, Tropical aspects of linear programming, Theses, École Polytechnique, December 2014.
- George M. Bergman, The logarithmic limit-set of an algebraic variety, Trans. Amer. Math. Soc. 157 (1971), 459–469. MR 280489, DOI 10.1090/S0002-9947-1971-0280489-8
- Robert Bieri and J. R. J. Groves, The geometry of the set of characters induced by valuations, J. Reine Angew. Math. 347 (1984), 168–195. MR 733052
- Anna Lena Birkmeyer, Andreas Gathmann, and Kirsten Schmitz, The realizability of curves in a tropical plane, Discrete Comput. Geom. 57 (2017), no. 1, 12–55. MR 3589056, DOI 10.1007/s00454-016-9816-0
- Alexandre V. Borovik, I. M. Gelfand, and Neil White, Coxeter matroids, Progress in Mathematics, vol. 216, Birkhäuser Boston, Inc., Boston, MA, 2003. MR 1989953, DOI 10.1007/978-1-4612-2066-4
- Walter Briec and Charles Horvath, $\Bbb B$-convexity, Optimization 53 (2004), no. 2, 103–127. MR 2058292, DOI 10.1080/02331930410001695283
- James R. Bunch and John E. Hopcroft, Triangular factorization and inversion by fast matrix multiplication, Math. Comp. 28 (1974), 231–236. MR 331751, DOI 10.1090/S0025-5718-1974-0331751-8
- Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999. MR 1744486, DOI 10.1007/978-3-662-12494-9
- Louis J. Billera, Susan P. Holmes, and Karen Vogtmann, Geometry of the space of phylogenetic trees, Adv. in Appl. Math. 27 (2001), no. 4, 733–767. MR 1867931, DOI 10.1006/aama.2001.0759
- Sarah Brodsky, Michael Joswig, Ralph Morrison, and Bernd Sturmfels, Moduli of tropical plane curves, Res. Math. Sci. 2 (2015), Art. 4, 31. MR 3333700, DOI 10.1186/s40687-014-0018-1
- Elizabeth Baldwin and Paul Klemperer, Understanding preferences: “demand types", and the existence of equilibrium with indivisibilities, Econometrica 87 (2019), no. 3, 867–932. MR 3957334, DOI 10.3982/ECTA13693
- Matthew Baker and Oliver Lorscheid, Descartes’ rule of signs, Newton polygons, and polynomials over hyperfields, J. Algebra 569 (2021), 416–441. MR 4187242, DOI 10.1016/j.jalgebra.2020.10.024
- Nicolas Bourbaki, Algebra II. Chapters 4–7, Elements of Mathematics (Berlin), Springer-Verlag, Berlin, 2003. Translated from the 1981 French edition by P. M. Cohn and J. Howie; Reprint of the 1990 English edition [Springer, Berlin; MR1080964 (91h:00003)]. MR 1994218, DOI 10.1007/978-3-642-61698-3
- Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. MR 2248869
- Matthew Baker, Sam Payne, and Joseph Rabinoff, Nonarchimedean geometry, tropicalization, and metrics on curves, Algebr. Geom. 3 (2016), no. 1, 63–105. MR 3455421, DOI 10.14231/AG-2016-004
- Matthias Beck and Sinai Robins, Computing the continuous discretely, 2nd ed., Undergraduate Texts in Mathematics, Springer, New York, 2015. Integer-point enumeration in polyhedra; With illustrations by David Austin. MR 3410115, DOI 10.1007/978-1-4939-2969-6
- Glen E. Bredon, Topology and geometry, Graduate Texts in Mathematics, vol. 139, Springer-Verlag, New York, 1997. Corrected third printing of the 1993 original. MR 1700700
- Walter Baur and Volker Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), no. 3, 317–330. MR 693063, DOI 10.1016/0304-3975(83)90110-X
- F. Bruhat and J. Tits, Groupes réductifs sur un corps local, Inst. Hautes Études Sci. Publ. Math. 41 (1972), 5–251 (French). MR 327923
- P. Butkovič, Regularity of matrices in min-algebra and its time-complexity, Discrete Appl. Math. 57 (1995), no. 2-3, 121–132. Combinatorial optimization 1992 (CO92) (Oxford). MR 1327771, DOI 10.1016/0166-218X(94)00099-Y
- Peter Butkovič, Max-linear systems: theory and algorithms, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2010. MR 2681232, DOI 10.1007/978-1-84996-299-5
- Florian Block and Josephine Yu, Tropical convexity via cellular resolutions, J. Algebraic Combin. 24 (2006), no. 1, 103–114. MR 2245783, DOI 10.1007/s10801-006-9104-9
- Desmond Coles, Neelav Dutta, Sifan Jiang, Ralph Morrison, and Andrew Scharf, Tropically planar graphs, 2020, Preprint arXiv:1908.04320.
- Freddy Cachazo and Nick Early, Minimal kinematics: An all $k$ and $n$ peek into $\operatorname {Trop}^+\operatorname {G}(k,n)$, 2020, Preprint arXiv:2003.07958.
- Freddy Cachazo, Nick Early, Alfredo Guevara, and Sebastian Mizera, Scattering equations: from projective spaces to tropical Grassmannians, J. High Energy Phys. 6 (2019), 039, 32. MR 3982543, DOI 10.1007/jhep06(2019)039
- Raymond Cuninghame-Green, Minimax algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer-Verlag, Berlin-New York, 1979. MR 580321
- Guy Cohen, Stéphane Gaubert, and Jean-Pierre Quadrat, Duality and separation theorems in idempotent semimodules, Linear Algebra Appl. 379 (2004), 395–422. Tenth Conference of the International Linear Algebra Society. MR 2039751, DOI 10.1016/j.laa.2003.08.010
- Guy Cohen, Stéphane Gaubert, Jean-Pierre Quadrat, and Ivan Singer, Max-plus convex sets and functions, Idempotent mathematics and mathematical physics, Contemp. Math., vol. 377, Amer. Math. Soc., Providence, RI, 2005, pp. 105–129. MR 2149000, DOI 10.1090/conm/377/06987
- T. M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete Comput. Geom. 16 (1996), no. 4, 361–368. Eleventh Annual Symposium on Computational Geometry (Vancouver, BC, 1995). MR 1414961, DOI 10.1007/BF02712873
- Türkü Özlüm Çelik, Asgar Jamneshan, Guido Montúfar, Bernd Sturmfels, and Lorenzo Venturello, Wasserstein distance to independence models, J. Symbolic Comput. 104 (2021), 855–873. MR 4180150, DOI 10.1016/j.jsc.2020.10.005
- Francisco Criado, Michael Joswig, and Francisco Santos, Tropical bisectors and Voronoi diagrams, 2019, Preprint arXiv:1906.10950.
- David A. Cox, John Little, and Donal O’Shea, Using algebraic geometry, 2nd ed., Graduate Texts in Mathematics, vol. 185, Springer, New York, 2005. MR 2122859
- David A. Cox, John B. Little, and Henry K. Schenck, Toric varieties, Graduate Studies in Mathematics, vol. 124, American Mathematical Society, Providence, RI, 2011. MR 2810322, DOI 10.1090/gsm/124
- Marcel Celaya, Georg Loho, and Chi Ho Yuen, Oriented matroids from triangulations of products of simplices, 2020, Preprint arXiv:2005.01787.
- Nathalie Caspard and Bernard Monjardet, The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Appl. Math. 127 (2003), no. 2, 241–269. The 1998 Conference on Ordinal and Symbolic Data Analysis (OSDA ’98) (Amherst, MA). MR 1984087, DOI 10.1016/S0166-218X(02)00209-3
- P. M. Cohn, Algebra. Vol. 2, 2nd ed., John Wiley & Sons, Ltd., Chichester, 1989. MR 1006872
- George E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975) Lecture Notes in Comput. Sci., Vol. 33, Springer, Berlin-New York, 1975, pp. 134–183. MR 403962
- Anne Condon, The complexity of stochastic games, Inform. and Comput. 96 (1992), no. 2, 203–224. MR 1147987, DOI 10.1016/0890-5401(92)90048-K
- Arnaud Costinot, An elementary theory of comparative advantage, Econometrica 77 (2009), no. 4, 1165–1192. MR 2547072, DOI 10.3982/ECTA7636
- Robert Alexander Crowell, The tropical division problem and the minkowski factorization of generalized permutahedra, 2019, Preprint arXiv:1908.00241.
- Mike Develin, The moduli space of $n$ tropically collinear points in $\Bbb R^d$, Collect. Math. 56 (2005), no. 1, 1–19. MR 2131129
- Jules Depersin, Stéphane Gaubert, and Michael Joswig, A tropical isoperimetric inequality, Sém. Lothar. Combin. 78B (2017), Art. 27, 12. MR 3678609
- Andreas Dress, Katharina T. Huber, Jacobus Koolen, Vincent Moulton, and Andreas Spillner, Basic phylogenetic combinatorics, Cambridge University Press, Cambridge, 2012. MR 2893879
- E. W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959), 269–271. MR 107609, DOI 10.1007/BF01386390
- Anton Dochtermann, Michael Joswig, and Raman Sanyal, Tropical types and associated cellular resolutions, J. Algebra 356 (2012), 304–324. MR 2891135, DOI 10.1016/j.jalgebra.2011.12.028
- Vladimir I. Danilov and Gleb A. Koshevoy, Discrete convexity and unimodularity. I, Adv. Math. 189 (2004), no. 2, 301–324. MR 2101223, DOI 10.1016/j.aim.2003.11.010
- Vladimir Danilov, Gleb Koshevoy, and Kazuo Murota, Discrete convexity and equilibria in economies with indivisible goods and money, Math. Social Sci. 41 (2001), no. 3, 251–273. MR 1818477, DOI 10.1016/S0165-4896(00)00071-8
- María Jesús de la Puente, On tropical Kleene star matrices and alcoved polytopes, Kybernetika (Prague) 49 (2013), no. 6, 897–910. MR 3182647
- M. J. de la Puente, Quasi-Euclidean classification of alcoved convex polyhedra, Linear Multilinear Algebra 68 (2020), no. 10, 2110–2142. MR 4160431, DOI 10.1080/03081087.2019.1572065
- Jesús A. De Loera, Jörg Rambau, and Francisco Santos, Triangulations, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010. Structures for algorithms and applications. MR 2743368, DOI 10.1007/978-3-642-12971-1
- Andreas W. M. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv. in Math. 53 (1984), no. 3, 321–402. MR 753872, DOI 10.1016/0001-8708(84)90029-X
- Mike Develin and Bernd Sturmfels, Tropical convexity, Doc. Math. 9 (2004), 1–27 (electronic), correction: ibid., pp. 205–206. MR 2054977
- Mike Develin, Francisco Santos, and Bernd Sturmfels, On the rank of a tropical matrix, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 213–242. MR 2178322
- Antoine Deza, Tamás Terlaky, and Yuriy Zinchenko, A continuous $d$-step conjecture for polytopes, Discrete Comput. Geom. 41 (2009), no. 2, 318–327. MR 2471877, DOI 10.1007/s00454-008-9096-4
- Andreas W. M. Dress and Walter Wenzel, Valuated matroids, Adv. Math. 93 (1992), no. 2, 214–250. MR 1164708, DOI 10.1016/0001-8708(92)90028-J
- Mike Develin and Josephine Yu, Tropical polytopes and cellular resolutions, Experiment. Math. 16 (2007), no. 3, 277–291. MR 2367318
- Jack Edmonds, Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 67–72. MR 190025
- Jack Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York-London-Paris, 1970, pp. 69–87. MR 270945
- Manfred Einsiedler, Mikhail Kapranov, and Douglas Lind, Non-Archimedean amoebas and tropical varieties, J. Reine Angew. Math. 601 (2006), 139–157. MR 2289207, DOI 10.1515/CRELLE.2006.097
- A. Ehrenfeucht and J. Mycielski, Positional strategies for mean payoff games, Internat. J. Game Theory 8 (1979), no. 2, 109–113. MR 550954, DOI 10.1007/BF01768705
- Samuel Eilenberg and Norman Steenrod, Foundations of algebraic topology, Princeton University Press, Princeton, NJ, 1952. MR 50886
- Günter Ewald, Combinatorial convexity and algebraic geometry, Graduate Texts in Mathematics, vol. 168, Springer-Verlag, New York, 1996. MR 1418400, DOI 10.1007/978-1-4612-4044-0
- Stefan Felsner and Kolja Knauer, Distributive lattices, polyhedra, and generalized flows, European J. Combin. 32 (2011), no. 1, 45–59. MR 2727459, DOI 10.1016/j.ejc.2010.07.011
- B. A. Farbey, A. H. Land, and J. D. Murchland, The cascade algorithm for finding all shortest distances in a directed graph, Management Sci. 14 (1967), 19–28. MR 241185, DOI 10.1287/mnsc.14.1.19
- Robert W. Floyd, Algorithm $97$ shortest path, Comm. Assoc. Comput. Mach. 5 (1962), 345.
- Alex Fink and Luca Moci, Matroids over a ring, J. Eur. Math. Soc. (JEMS) 18 (2016), no. 4, 681–731. MR 3474454, DOI 10.4171/JEMS/600
- Alex Fink and Jorge Alberto Olarte, Presentations of transversal valuated matroids, 2020, Preprint arXiv:1903.08288.
- Lester R. Ford, Jr., Network flow theory, Tech. report, The RAND Corporation, Paper P-923, 1956.
- Alex Fink and Felipe Rincón, Stiefel tropical linear spaces, J. Combin. Theory Ser. A 135 (2015), 291–331. MR 3366480, DOI 10.1016/j.jcta.2015.06.001
- Eva Maria Feichtner and Bernd Sturmfels, Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.) 62 (2005), no. 4, 437–468. MR 2191630
- Satoru Fujishige, A characterization of faces of the base polyhedron associated with a submodular system, J. Oper. Res. Soc. Japan 27 (1984), no. 2, 112–129 (English, with Japanese summary). MR 755473, DOI 10.15807/jorsj.27.112
- Tibor Gallai, Maximum-minimum Sätze über Graphen, Acta Math. Acad. Sci. Hungar. 9 (1958), 395–434 (German). MR 124238, DOI 10.1007/BF02020271
- Bernhard Ganter, Algorithmen zur formalen Begriffsanalyse, Beiträge zur Begriffsanalyse (Darmstadt, 1986) Bibliographisches Inst., Mannheim, 1987, pp. 241–254 (German). MR 949457
- Stéphane Gaubert, Theory of linear systems over dioids, Ph.D. thesis, Ecole Nationale Supérieure des Mines de Paris, 1992.
- Stéphane Gaubert and Jeremy Gunawardena, The duality theorem for min-max functions, C. R. Acad. Sci. Paris Sér. I Math. 326 (1998), no. 1, 43–48 (English, with English and French summaries). MR 1649473, DOI 10.1016/S0764-4442(97)82710-3
- I. M. Gel′fand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. in Math. 63 (1987), no. 3, 301–316. MR 877789, DOI 10.1016/0001-8708(87)90059-4
- Israel M. Gelfand, Mark I. Graev, and Alexander Postnikov, Combinatorics of hypergeometric functions associated with positive roots, The Arnold-Gelfand mathematical seminars, Birkhäuser Boston, Boston, MA, 1997, pp. 205–221. MR 1429893, DOI 10.1007/978-1-4612-4122-5_{1}0
- Étienne Ghys, A singular mathematical promenade, ENS Éditions, Lyon, 2017. MR 3702027
- Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979. A guide to the theory of NP-completeness. MR 519066
- Ewgenij Gawrilow and Michael Joswig, polymake: a framework for analyzing convex polytopes, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 43–73. MR 1785292
- Bernd Gärtner and Martin Jaggi, Tropical support vector machines, ACS Technical Report No.: ACS-TR-362502-01, 2006.
- Stéphane Gaubert and Ricardo D. Katz, Minimal half-spaces and external representation of tropical polyhedra, J. Algebraic Combin. 33 (2011), no. 3, 325–348. MR 2772536, DOI 10.1007/s10801-010-0246-4
- V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan, Cyclic games and finding minimax mean cycles in digraphs, Zh. Vychisl. Mat. i Mat. Fiz. 28 (1988), no. 9, 1407–1417, 1439 (Russian); English transl., U.S.S.R. Comput. Math. and Math. Phys. 28 (1988), no. 5, 85–91 (1990). MR 967535, DOI 10.1016/0041-5553(88)90012-2
- Andreas Gathmann, Michael Kerber, and Hannah Markwig, Tropical fans and the moduli spaces of tropical curves, Compos. Math. 145 (2009), no. 1, 173–195. MR 2480499, DOI 10.1112/S0010437X08003837
- Stéphane Gaubert, Ricardo D. Katz, and Sergeĭ Sergeev, Tropical linear-fractional programming and parametric mean payoff games, J. Symbolic Comput. 47 (2012), no. 12, 1447–1478. MR 2929038, DOI 10.1016/j.jsc.2011.12.049
- I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants and multidimensional determinants, Modern Birkhäuser Classics, Birkhäuser Boston, Inc., Boston, MA, 2008. Reprint of the 1994 edition. MR 2394437
- S. Gao and A. G. B. Lauder, Decomposition of polytopes and polynomials, Discrete Comput. Geom. 26 (2001), no. 1, 89–104. MR 1832732, DOI 10.1007/s00454-001-0024-0
- Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, 2nd ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR 1261419, DOI 10.1007/978-3-642-78240-4
- Andreas Gathmann and Hannah Markwig, The Caporaso-Harris formula and plane relative Gromov-Witten invariants in tropical geometry, Math. Ann. 338 (2007), no. 4, 845–868. MR 2317753, DOI 10.1007/s00208-007-0092-4
- Michel Gondran and Michel Minoux, Graphs, dioids and semirings, Operations Research/Computer Science Interfaces Series, vol. 41, Springer, New York, 2008. New models and algorithms. MR 2389137
- Stéphane Gaubert and Frédéric Meunier, Carathéodory, Helly and the others in the max-plus world, Discrete Comput. Geom. 43 (2010), no. 3, 648–662. MR 2587842, DOI 10.1007/s00454-009-9207-x
- Stéphane Gaubert and Marie MacCaig, Approximating the volume of tropical polytopes is difficult, Internat. J. Algebra Comput. 29 (2019), no. 2, 357–389. MR 3934791, DOI 10.1142/S0218196719500061
- Bernhard Ganter and Sergei Obiedkov, Conceptual exploration, Springer-Verlag, Berlin, 2016. MR 3495406, DOI 10.1007/978-3-662-49291-8
- Dima Grigoriev and Vladimir V. Podolskii, Complexity of tropical and min-plus linear prevarieties, Comput. Complexity 24 (2015), no. 1, 31–64. MR 3320301, DOI 10.1007/s00037-013-0077-5
- Dima Grigoriev and Vladimir V. Podolskii, Tropical effective primary and dual Nullstellensätze, Discrete Comput. Geom. 59 (2018), no. 3, 507–552. MR 3770201, DOI 10.1007/s00454-018-9966-3
- Dima Grigoriev, Complexity of solving tropical linear systems, Comput. Complexity 22 (2013), no. 1, 71–88. MR 3034020, DOI 10.1007/s00037-012-0053-5
- Branko Grünbaum, Convex polytopes, 2nd ed., Graduate Texts in Mathematics, vol. 221, Springer-Verlag, New York, 2003. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler. MR 1976856, DOI 10.1007/978-1-4613-0019-9
- Alexander Guterman and Yaroslav Shitov, Rank functions of tropical matrices, Linear Algebra Appl. 498 (2016), 326–348. MR 3478565, DOI 10.1016/j.laa.2015.07.004
- Walter Gubler, Tropical varieties for non-Archimedean analytic spaces, Invent. Math. 169 (2007), no. 2, 321–376. MR 2318559, DOI 10.1007/s00222-007-0048-z
- Walter Gubler, A guide to tropicalizations, Algebraic and combinatorial aspects of tropical geometry, Contemp. Math., vol. 589, Amer. Math. Soc., Providence, RI, 2013, pp. 125–189. MR 3088913, DOI 10.1090/conm/589/11745
- Dima Grigoriev and Nicolai Vorobjov, Complexity of deciding whether a tropical linear prevariety is a tropical variety, Appl. Algebra Engrg. Comm. Comput. 32 (2021), no. 2, 157–174. MR 4216369, DOI 10.1007/s00200-019-00407-w
- I. M. Gel′fand, A. V. Zelevinskiĭ, and M. M. Kapranov, Discriminants of polynomials in several variables and triangulations of Newton polyhedra, Algebra i Analiz 2 (1990), no. 3, 1–62 (Russian); English transl., Leningrad Math. J. 2 (1991), no. 3, 449–505. MR 1073208
- John Harris (ed.), Lexicon technicum: or, a universal English dictionary of arts and sciences: explaining not only the terms of art, but the arts themselves, vol. 2, London, 1710.
- Daniel H. Huson and David Bryant, \splitstree, https://github.com/husonlab/splitstree4, retrieved 03 March 2021.
- Daniel H. Huson and David Bryant, Application of phylogenetic networks in evolutionary studies, Mol. Biol. Evol. 23 (2006), no. 2, 254–267.
- Siegfried Helbig, On Carathéodory’s and Kreĭn-Milman’s theorems in fully ordered groups, Comment. Math. Univ. Carolin. 29 (1988), no. 1, 157–167. MR 937558
- Hiroshi Hirai, A geometric study of the split decomposition, Discrete Comput. Geom. 36 (2006), no. 2, 331–361. MR 2252108, DOI 10.1007/s00454-006-1243-1
- Sven Herrmann and Michael Joswig, Splitting polytopes, Münster J. Math. 1 (2008), 109–141. MR 2502496
- Sven Herrmann and Michael Joswig, Totally splittable polytopes, Discrete Comput. Geom. 44 (2010), no. 1, 149–166. MR 2639822, DOI 10.1007/s00454-009-9217-8
- Simon Hampe and Michael Joswig, Tropical computations in $\tt {polymake}$, Algorithmic and experimental methods in algebra, geometry, and number theory, Springer, Cham, 2017, pp. 361–385. MR 3792732
- Sven Herrmann, Anders Jensen, Michael Joswig, and Bernd Sturmfels, How to draw tropical planes, Electron. J. Combin. 16 (2009), no. 2, Special volume in honor of Anders Björner, Research Paper 6, 26. MR 2515769, DOI 10.37236/72
- Sven Herrmann, Michael Joswig, and Marc E. Pfetsch, Computing the bounded subcomplex of an unbounded polyhedron, Comput. Geom. 46 (2013), no. 5, 541–551. MR 3015940, DOI 10.1016/j.comgeo.2011.11.002
- Sven Herrmann, Michael Joswig, and David E. Speyer, Dressians, tropical Grassmannians, and their rays, Forum Math. 26 (2014), no. 6, 1853–1881. MR 3334049, DOI 10.1515/forum-2012-0030
- Simon Hampe, Michael Joswig, and Benjamin Schröter, Algorithms for tight spans and tropical linear spaces, J. Symbolic Comput. 91 (2019), 116–128. MR 3860887, DOI 10.1016/j.jsc.2018.06.016
- Hiroshi Hirai and Shungo Koichi, On tight spans for directed distances, Ann. Comb. 16 (2012), no. 3, 543–569. MR 2960019, DOI 10.1007/s00026-012-0146-5
- Cvetelina Hill, Sara Lamboglia, and Faye Pasley Simon, Tropical convex hulls of infinite sets, 2019, Preprint arXiv:1912.01253.
- Sven Herrmann and Vincent Moulton, Trees, tight-spans and point configurations, Discrete Math. 312 (2012), no. 16, 2506–2521. MR 2927167, DOI 10.1016/j.disc.2012.05.003
- Silke Horn, A topological representation theorem for tropical oriented matroids, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), Discrete Math. Theor. Comput. Sci. Proc., AR, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012, pp. 135–146 (English, with English and French summaries). MR 2957992
- Birkett Huber, Jörg Rambau, and Francisco Santos, The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings, J. Eur. Math. Soc. (JEMS) 2 (2000), no. 2, 179–198. MR 1763304, DOI 10.1007/s100970050003
- Serkan Hoşten and Bernd Sturmfels, Computing the integer programming gap, Combinatorica 27 (2007), no. 3, 367–382. MR 2345814, DOI 10.1007/s00493-007-2057-3
- James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
- N. Iwahori and H. Matsumoto, On some Bruhat decomposition and the structure of the Hecke rings of ${\mathfrak {p}}$-adic Chevalley groups, Inst. Hautes Études Sci. Publ. Math. 25 (1965), 5–48. MR 185016
- Ilia Itenberg, Grigory Mikhalkin, and Eugenii Shustin, Tropical algebraic geometry, 2nd ed., Oberwolfach Seminars, vol. 35, Birkhäuser Verlag, Basel, 2009. MR 2508011, DOI 10.1007/978-3-0346-0048-4
- OEIS Foundation Inc., The on-line encyclopedia of integer sequences, http://oeis.org/A001147, 2020.
- Zur Izhakian and Louis Rowen, The tropical rank of a tropical matrix, Comm. Algebra 37 (2009), no. 11, 3912–3927. MR 2573227, DOI 10.1080/00927870902828793
- Hiroshi Iriyeh and Masataka Shibata, Symmetric Mahler’s conjecture for the volume product in the $3$-dimensional case, Duke Math. J. 169 (2020), no. 6, 1077–1134. MR 4085078, DOI 10.1215/00127094-2019-0072
- J. R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964), 65–76. MR 182949, DOI 10.1007/BF02566944
- Ilia Itenberg and Oleg Viro, Patchworking algebraic curves disproves the Ragsdale conjecture, Math. Intelligencer 18 (1996), no. 4, 19–28. MR 1413249, DOI 10.1007/BF03026748
- Nathan Jacobson, Basic algebra. II, 2nd ed., W. H. Freeman and Company, New York, 1989. MR 1009787
- Andrea Jiménez and María Jesús de la Puente, Six combinatorial classes of maximal convex tropical polyhedra, 2012, Preprint arXiv:1205.4162.
- Anders Nedergaard Jensen, Traversing symmetric polyhedral fans, Mathematical software—ICMS 2010, Lecture Notes in Comput. Sci., vol. 6327, Springer, Berlin, 2010, pp. 282–294. MR 3663204
- Anders Nedergaard Jensen, \gfan, a software system for Gröbner fans and tropical varieties, version 0.6.2, Available at http://home.imf.au.dk/jensen/software/gfan/gfan.html, 2017.
- Robert G. Jeroslow, Asymptotic linear programming, Operations Research 21 (1973), no. 5, 1128–1141.
- Charles Jordan, Michael Joswig, and Lars Kastner, Parallel enumeration of triangulations, Electron. J. Combin. 25 (2018), no. 3, Paper No. 3.6, 27. MR 3829292, DOI 10.37236/7318
- Charles Jordan, Michael Joswig, and Lars Kastner, \mptopcom, version 1.2, 2020, Open source software for the parallel enumeration of triangulations, http://www.polymake.org/mptopcom.
- Michael Joswig and Katja Kulas, Tropical and ordinary convexity combined, Adv. Geom. 10 (2010), no. 2, 333–352. MR 2629819, DOI 10.1515/ADVGEOM.2010.012
- C. N. Jones, E. C. Kerrigan, and J. M. Maciejowski, On polyhedral projection and parametric programming, J. Optim. Theory Appl. 138 (2008), no. 2, 207–220. MR 2414994, DOI 10.1007/s10957-008-9384-4
- Michael Joswig and Georg Loho, Weighted digraphs and tropical cones, Linear Algebra Appl. 501 (2016), 304–343. MR 3485070, DOI 10.1016/j.laa.2016.02.027
- Michael Joswig and Georg Loho, Monomial tropical cones for multicriteria optimization, SIAM J. Discrete Math. 34 (2020), no. 2, 1172–1191. MR 4101364, DOI 10.1137/17M1153066
- Michael Joswig, Georg Loho, Benjamin Lorenz, and Benjamin Schröter, Linear programs and convex hulls over fields of Puiseux fractions, Mathematical aspects of computer and information sciences, Lecture Notes in Comput. Sci., vol. 9582, Springer, [Cham], 2016, pp. 429–445. MR 3517052, DOI 10.1007/978-3-319-32859-1_{3}7
- Michael Joswig, Tropical halfspaces, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 409–431. MR 2178330
- Michael Joswig, The Cayley trick for tropical hypersurfaces with a view toward Ricardian economics, Homological and computational methods in commutative algebra, Springer INdAM Ser., vol. 20, Springer, Cham, 2017, pp. 107–128. MR 3751882
- Michael Joswig and Benjamin Schröter, Matroids from hypersimplex splits, J. Combin. Theory Ser. A 151 (2017), 254–284. MR 3663497, DOI 10.1016/j.jcta.2017.05.001
- Michael Joswig and Benjamin Schröter, Parametric shortest-path algorithms via tropical geometry, 2020, Preprint arXiv:1904.01082v3.
- Michael Joswig, Bernd Sturmfels, and Josephine Yu, Affine buildings and tropical convexity, Albanian J. Math. 1 (2007), no. 4, 187–211. MR 2367213
- Philipp Jell, Claus Scheiderer, and Josephine Yu, Real tropicalization and analytification of semialgebraic sets, 2018, Preprint arXiv:1810.05132.
- Michael Joswig and Thorsten Theobald, Polyhedral and algebraic methods in computational geometry, Universitext, Springer, London, 2013. Revised and updated translation of the 2008 German original. MR 2905853, DOI 10.1007/978-1-4471-4817-3
- Michael Joswig and Ayush Kumar Tewari, Forbidden patterns in tropical plane curves, Beitr. Algebra Geom. 62 (2021), no. 1, 65–81. MR 4249854, DOI 10.1007/s13366-020-00523-6
- M. M. Kapranov, Chow quotients of Grassmannians. I, I. M. Gel′fand Seminar, Adv. Soviet Math., vol. 16, Amer. Math. Soc., Providence, RI, 1993, pp. 29–110. MR 1237834
- Richard M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Math. 23 (1978), no. 3, 309–311. MR 523080, DOI 10.1016/0012-365X(78)90011-0
- N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984), no. 4, 373–395. MR 779900, DOI 10.1007/BF02579150
- L. G. Hačijan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR 244 (1979), no. 5, 1093–1096 (Russian). MR 522052
- Gil Kalai and Daniel J. Kleitman, A quasi-polynomial bound for the diameter of graphs of polyhedra, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 315–316. MR 1130448, DOI 10.1090/S0273-0979-1992-00285-9
- Alexander V. Karzanov and Vasilij N. Lebedev, Cyclical games with prohibitions, Math. Programming 60 (1993), no. 3, Ser. A, 277–293. MR 1234877, DOI 10.1007/BF01580616
- M. Krein and D. Milman, On extreme points of regular convex sets, Studia Math. 9 (1940), 133–138 (English, with Ukrainian summary). MR 4990, DOI 10.4064/sm-9-1-133-138
- Victor Klee and George J. Minty, How good is the simplex algorithm?, Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), Academic Press, New York-London, 1972, pp. 159–175. MR 332165
- Anthony W. Knapp, Basic algebra, Cornerstones, Birkhäuser Boston, Inc., Boston, MA, 2006. Along with a companion volume Advanced algebra. MR 2257570, DOI 10.1007/978-0-8176-4529-8
- Maxim Kontsevich, Intersection theory on the moduli space of curves and the matrix Airy function, Comm. Math. Phys. 147 (1992), no. 1, 1–23. MR 1171758
- Dmitry Kozlov, Combinatorial algebraic topology, Algorithms and Computation in Mathematics, vol. 21, Springer, Berlin, 2008. MR 2361455, DOI 10.1007/978-3-540-71962-5
- Volker Kaibel and Marc E. Pfetsch, Computing the face lattice of a polytope from its vertex-facet incidences, Comput. Geom. 23 (2002), no. 3, 281–290. MR 1927137, DOI 10.1016/S0925-7721(02)00103-7
- Volker Kaibel and Marc E. Pfetsch, Some algorithmic problems in polytope theory, Algebra, geometry, and software systems, Springer, Berlin, 2003, pp. 23–47. MR 2011752
- K. H. Kim and F. W. Roush, Kapranov rank vs. tropical rank, Proc. Amer. Math. Soc. 134 (2006), no. 9, 2487–2494. MR 2213725, DOI 10.1090/S0002-9939-06-08426-7
- Marc Krasner, Approximation des corps valués complets de caractéristique $p\not =0$ par ceux de caractéristique $0$, Colloque d’algèbre supérieure, tenu à Bruxelles du 19 au 22 décembre 1956, Centre Belge de Recherches Mathématiques, Établissements Ceuterick, Louvain, 1957, pp. 129–206 (French). MR 106218
- Edward D. Kim and Francisco Santos, An update on the Hirsch conjecture, Jahresber. Dtsch. Math.-Ver. 112 (2010), no. 2, 73–98. MR 2681516, DOI 10.1365/s13291-010-0001-8
- Sean Keel and Jenia Tevelev, Geometry of Chow quotients of Grassmannians, Duke Math. J. 134 (2006), no. 2, 259–311. MR 2248832, DOI 10.1215/S0012-7094-06-13422-1
- J. J. Kosowsky and Alan L. Yuille, The invisible hand algorithm: Solving the assignment problem with statistical physics, Neural Networks 7 (1994), no. 3, 477–490.
- G. L. Litvinov, V. P. Maslov, and G. B. Shpiz, Idempotent functional analysis. An algebraic approach, Mat. Zametki 69 (2001), no. 5, 758–797 (Russian, with Russian summary); English transl., Math. Notes 69 (2001), no. 5-6, 696–729. MR 1846814, DOI 10.1023/A:1010266012029
- Georg Loho, Combinatorics of tropical linear programming, Ph.D. thesis, TU Berlin, 2017.
- Georg Loho, Abstract tropical linear programming, Electron. J. Combin. 27 (2020), no. 2, Paper No. 2.51, 68. MR 4245106, DOI 10.37236/7718
- Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of computation, 2nd ed., Prentice Hall, 1998.
- Thomas Lam and Alexander Postnikov, Alcoved polytopes. I, Discrete Comput. Geom. 38 (2007), no. 3, 453–478. MR 2352704, DOI 10.1007/s00454-006-1294-3
- Georg Loho and Matthias Schymura, Tropical Ehrhart theory and tropical volume, Res. Math. Sci. 7 (2020), no. 4, Paper No. 30, 34. MR 4155409, DOI 10.1007/s40687-020-00228-1
- Georg Loho and Ben Smith, Matching fields and lattice points of simplices, Adv. Math. 370 (2020), 107232, 42. MR 4104819, DOI 10.1016/j.aim.2020.107232
- Bo Lin, Bernd Sturmfels, Xiaoxian Tang, and Ruriko Yoshida, Convexity in tree spaces, SIAM J. Discrete Math. 31 (2017), no. 3, 2015–2038. MR 3693600, DOI 10.1137/16M1079841
- Bo Lin and Ngoc Mai Tran, Two-player incentive compatible outcome functions are affine maximizers, Linear Algebra Appl. 578 (2019), 133–152. MR 3950503, DOI 10.1016/j.laa.2019.04.027
- A. G. Lunc, Algebraic methods of analysis and synthesis of relay contact networks, Izv. Akad. Nauk SSSR Ser. Mat. 16 (1952), 405–436 (Russian). MR 52324
- Georg Loho and László A. Végh, Signed tropical convexity, 2019, Preprint arXiv:1906.06686.
- Bo Lin and Ruriko Yoshida, Tropical Fermat-Weber points, SIAM J. Discrete Math. 32 (2018), no. 2, 1229–1245. MR 3810501, DOI 10.1137/16M1071122
- Kurt Mahler, Ein Minimalproblem für konvexe Polygone (German), Mathematica B, Zutphen 7 (1938), 118–127.
- Kurt Mahler, Ein Übertragungsprinzip für konvexe Körper, Časopis Pěst. Mat. Fys. 68 (1939), 93–102 (German). MR 1242
- T. Markwig, A field of generalised Puiseux series for tropical geometry, Rend. Semin. Mat. Univ. Politec. Torino 68 (2010), no. 1, 79–92. MR 2759691
- V. P. Maslov, On a new superposition principle for optimization problem, Séminaire sur les équations aux dérivées partielles, 1985–1986, École Polytech., Palaiseau, 1986, pp. Exp. No. XXIV, 14. MR 874583
- Bassel Mannaa and Thierry Coquand, Dynamic Newton-Puiseux theorem, J. Log. Anal. 5 (2013), Paper 5, 22. MR 3066398, DOI 10.4115/jla.2013.5.5
- P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
- Peter McMullen, The polytope algebra, Adv. Math. 78 (1989), no. 1, 76–130. MR 1021549, DOI 10.1016/0001-8708(89)90029-7
- Nimrod Megiddo, On the complexity of linear programming, Advances in economic theory (Cambridge, MA, 1985) Econom. Soc. Monogr., vol. 12, Cambridge Univ. Press, Cambridge, 1989, pp. 225–268. MR 1117042
- Grigory Mikhalkin, Enumerative tropical algebraic geometry in $\Bbb R^2$, J. Amer. Math. Soc. 18 (2005), no. 2, 313–377. MR 2137980, DOI 10.1090/S0894-0347-05-00477-7
- Grigory Mikhalkin, Tropical geometry and its applications, International Congress of Mathematicians. Vol. II, Eur. Math. Soc., Zürich, 2006, pp. 827–852. MR 2275625
- Gr. C. Moisil, Sur une représentation des graphes qui interviennent dans l’économie des transports, Com. Acad. R. P. Romîne 10 (1960), 647–652 (Romanian, with French and Russian summaries). MR 136445
- T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, The double description method, Contributions to the theory of games, vol. 2, Ann. of Math. Stud., no. 28, Princeton Univ. Press, Princeton, NJ, 1953, pp. 51–73. MR 60202
- Guido Montúfar, Yue Ren, and Leon Zhang, Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums, 2021, Preprint arXiv:2104.08135.
- Diane Maclagan and Bernd Sturmfels, Introduction to tropical geometry, Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015. MR 3287221, DOI 10.1090/gsm/161
- Rolf H. Möhring, Martin Skutella, and Frederik Stork, Scheduling with AND/OR precedence constraints, SIAM J. Comput. 33 (2004), no. 2, 393–415. MR 2048448, DOI 10.1137/S009753970037727X
- Kazuo Murota and Akihisa Tamura, On circuit valuation of matroids, Adv. in Appl. Math. 26 (2001), no. 3, 192–225. MR 1818743, DOI 10.1006/aama.2000.0716
- Kazuo Murota, Discrete convex analysis, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. MR 1997998, DOI 10.1137/1.9780898718508
- Peter Nelson, Almost all matroids are nonrepresentable, Bull. Lond. Math. Soc. 50 (2018), no. 2, 245–248. MR 3830117, DOI 10.1112/blms.12141
- Fedor Nazarov, Fedor Petrov, Dmitry Ryabogin, and Artem Zvavitch, A remark on the Mahler conjecture: local minimality of the unit cube, Duke Math. J. 154 (2010), no. 3, 419–430. MR 2730574, DOI 10.1215/00127094-2010-042
- Jorge Alberto Olarte, Marta Panizzut, and Benjamin Schröter, On local Dressians of matroids, Algebraic and geometric combinatorics on lattice polytopes, World Sci. Publ., Hackensack, NJ, 2019, pp. 309–329. MR 3971702
- G. J. Olsder and C. Roos, Cramér and Cayley-Hamilton in the max algebra, Linear Algebra Appl. 101 (1988), 87–108. MR 941298, DOI 10.1016/0024-3795(88)90145-0
- Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300, Springer-Verlag, Berlin, 1992. MR 1217488, DOI 10.1007/978-3-662-02772-1
- James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819, DOI 10.1093/acprof:oso/9780198566946.001.0001
- Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
- Sam Payne, Analytification is the limit of all tropicalizations, Math. Res. Lett. 16 (2009), no. 3, 543–556. MR 2511632, DOI 10.4310/MRL.2009.v16.n3.a13
- Alexander Postnikov, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN 6 (2009), 1026–1106. MR 2487491, DOI 10.1093/imrn/rnn153
- Julian Pfeifle and Jörg Rambau, Computing triangulations using oriented matroids, Algebra, geometry, and software systems, Springer, Berlin, 2003, pp. 49–75. MR 2011753
- Alex Postnikov, Victor Reiner, and Lauren Williams, Faces of generalized permutohedra, Doc. Math. 13 (2008), 207–273. MR 2520477
- Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1982. MR 663728
- Lior Pachter and Bernd Sturmfels (eds.), Algebraic statistics for computational biology, Cambridge University Press, New York, 2005. MR 2205865, DOI 10.1017/CBO9780511610684
- Jörg Rambau, TOPCOM: triangulations of point configurations and oriented matroids, Mathematical software (Beijing, 2002) World Sci. Publ., River Edge, NJ, 2002, pp. 330–340. MR 1932619
- Jörg Rambau, \TOPCOM, version 0.17.8, available at http://www.rambau.wm.uni-bayreuth.de/TOPCOM/, 2019.
- James Renegar, A polynomial-time algorithm, based on Newton’s method, for linear programming, Math. Programming 40 (1988), no. 1, (Ser. A), 59–93. MR 923697, DOI 10.1007/BF01580724
- James Renegar, A mathematical view of interior-point methods in convex optimization, MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2001. MR 1857706, DOI 10.1137/1.9780898718812
- Jürgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald, First steps in tropical geometry, Idempotent mathematics and mathematical physics, Contemp. Math., vol. 377, Amer. Math. Soc., Providence, RI, 2005, pp. 289–317. MR 2149011, DOI 10.1090/conm/377/06998
- David Ricardo, On the principles of political economy and taxation, London, John Murray, 1817.
- David Ricardo, On the principles of political economy and taxation, Cambridge Library Collection – British and Irish History, 19th Century, Cambridge: Cambridge University Press, 2015.
- Felipe Rincón, Computing tropical linear spaces, J. Symbolic Comput. 51 (2013), 86–98. MR 3005783, DOI 10.1016/j.jsc.2012.03.008
- Q. I. Rahman and G. Schmeisser, Analytic theory of polynomials, London Mathematical Society Monographs. New Series, vol. 26, The Clarendon Press, Oxford University Press, Oxford, 2002. MR 1954841
- Günter Rote, Francisco Santos, and Ileana Streinu, Expansive motions and the polytope of pointed pseudo-triangulations, Discrete and computational geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 699–736. MR 2038499, DOI 10.1007/978-3-642-55566-4_{3}3
- Neil Robertson, P. D. Seymour, and Robin Thomas, Permanents, Pfaffian orientations, and even directed circuits, Ann. of Math. (2) 150 (1999), no. 3, 929–975. MR 1740989, DOI 10.2307/121059
- Francisco Santos, A counterexample to the Hirsch conjecture, Ann. of Math. (2) 176 (2012), no. 1, 383–412. MR 2925387, DOI 10.4007/annals.2012.176.1.7
- Randall T. Schuh and Andrew Van Zandt Brower, Biological systematics: Principles and applications, Cornell University Press, 2017.
- Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
- Alexander Schrijver, Combinatorial optimization. Polyhedra and efficiency. Vol. A, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003. Paths, flows, matchings; Chapters 1–38. MR 1956924
- Raimund Seidel, Convex hull computations, Handbook of Discrete and Computational Geometry (Csaba D. Tóth, Jacob E. Goodmann, and Joseph O’Rourke, eds.), 3rd ed., CRC Press, Boca Raton, FL, 2018.
- H. Salzmann, T. Grundhöfer, H. Hähl, and R. Löwen, The classical fields, Encyclopedia of Mathematics and its Applications, vol. 112, Cambridge University Press, Cambridge, 2007. Structural features of the real and rational numbers. MR 2357231, DOI 10.1017/CBO9780511721502
- Yoshinori Shiozawa, International trade theory and exotic algebras, Evolut. Inst. Econ. Rev. 12 (2015), no. 1, 177–212.
- Imre Simon, Limited subsets of a free monoid, 19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., 1978) IEEE, Long Beach, CA, 1978, pp. 143–150. MR 539835
- Imre Simon, Recognizable sets with multiplicities in the tropical semiring, Mathematical foundations of computer science, 1988 (Carlsbad, 1988) Lecture Notes in Comput. Sci., vol. 324, Springer, Berlin, 1988, pp. 107–120. MR 1023416, DOI 10.1007/BFb0017135
- Steve Smale, Mathematical problems for the next century, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 271–294. MR 1754783
- David E. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (2008), no. 4, 1527–1558. MR 2448909, DOI 10.1137/080716219
- David E. Speyer, A matroid invariant via the $K$-theory of the Grassmannian, Adv. Math. 221 (2009), no. 3, 882–913. MR 2511042, DOI 10.1016/j.aim.2009.01.010
- David Speyer and Bernd Sturmfels, The tropical Grassmannian, Adv. Geom. 4 (2004), no. 3, 389–411. MR 2071813, DOI 10.1515/advg.2004.023
- Sergeĭ Sergeev, Hans Schneider, and Peter Butkovič, On visualization scaling, subeigenvectors and Kleene stars in max algebra, Linear Algebra Appl. 431 (2009), no. 12, 2395–2406. MR 2563030, DOI 10.1016/j.laa.2009.03.040
- Bernd Sturmfels and Ngoc Mai Tran, Combinatorial types of tropical eigenvectors, Bull. Lond. Math. Soc. 45 (2013), no. 1, 27–36. MR 3033951, DOI 10.1112/blms/bds058
- Richard P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1 (1986), no. 1, 9–23. MR 824105, DOI 10.1007/BF02187680
- Richard P. Stanley, Enumerative combinatorics. Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR 2868112
- Ernst Steinitz, Algebraische Theorie der Körper, J. Reine Angew. Math. 137 (1910), 167–309 (German). MR 1580791, DOI 10.1515/crll.1910.137.167
- Stefan Straszewicz, Über exponierte Punkte abgeschlossener Punktmengen, Fundam. Math. 24 (1935), 139–143.
- Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
- Bernd Sturmfels, On the Newton polytope of the resultant, J. Algebraic Combin. 3 (1994), no. 2, 207–236. MR 1268576, DOI 10.1023/A:1022497624378
- Bernd Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996. MR 1363949, DOI 10.1090/ulect/008
- Bernd Sturmfels, Solving systems of polynomial equations, CBMS Regional Conference Series in Mathematics, vol. 97, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2002. MR 1925796, DOI 10.1090/cbms/097
- David Speyer and Lauren K. Williams, The positive Dressian equals the positive tropical Grassmannian, Trans. Amer. Math. Soc. Ser. B 8 (2021), 330–353. MR 4241765, DOI 10.1090/btran/67
- Bernd Sturmfels and Josephine Yu, Classification of six-point metrics, Electron. J. Combin. 11 (2004), no. 1, Research Paper 44, 16. MR 2097310, DOI 10.37236/1797
- Terence Tao, Structure and randomness, American Mathematical Society, Providence, RI, 2008. Pages from year one of a mathematical blog. MR 2459552, DOI 10.1090/mbk/059
- Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley-Los Angeles, Calif., 1951. 2nd ed. MR 44472
- Rekha R. Thomas, Lectures in geometric combinatorics, Student Mathematical Library, vol. 33, American Mathematical Society, Providence, RI; Institute for Advanced Study (IAS), Princeton, NJ, 2006. IAS/Park City Mathematical Subseries. MR 2237292, DOI 10.1090/stml/033
- Jacques Tits, Buildings of spherical type and finite BN-pairs, Lecture Notes in Mathematics, Vol. 386, Springer-Verlag, Berlin-New York, 1974. MR 470099
- Ngoc Mai Tran, Enumerating polytropes, J. Combin. Theory Ser. A 151 (2017), 1–22. MR 3663485, DOI 10.1016/j.jcta.2017.03.011
- Xiaoxian Tang, Houjie Wang, and Ruriko Yoshida, Tropical support vector machine and its applications to phylogenomics, 2020, Preprint arXiv:2003.00677.
- Ngoc Mai Tran and Josephine Yu, Product-mix auctions and tropical geometry, Math. Oper. Res. 44 (2019), no. 4, 1396–1411. MR 4032448, DOI 10.1287/moor.2018.0975
- Henryk Trappmann and Günter M. Ziegler, Shellability of complexes of trees, J. Combin. Theory Ser. A 82 (1998), no. 2, 168–178. MR 1620865, DOI 10.1006/jcta.1997.2844
- Lou van den Dries and Patrick Speissegger, The real field with convergent generalized power series, Trans. Amer. Math. Soc. 350 (1998), no. 11, 4377–4421. MR 1458313, DOI 10.1090/S0002-9947-98-02105-9
- Bartel L. van der Waerden, Algebra II. Unter Benutzung von Vorlesungen von E. Artin und E. Noether. Mit einem Geleitwort von Jürgen Neukirch (German), 6th ed., Springer, Berlin, 1993.
- Oleg Viro, Dequantization of real algebraic geometry on logarithmic paper, European Congress of Mathematics, Vol. I (Barcelona, 2000) Progr. Math., vol. 201, Birkhäuser, Basel, 2001, pp. 135–146. MR 1905317
- Nikolaĭ Nikolaevič Vorob′ev, Extremal algebra of positive matrices, Elektron. Informationsverarb. Kybernet. 3 (1967), 39–71 (Russian, with English and Russian summaries). MR 216854
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
- Martin J. Wainwright, High-dimensional statistics, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 48, Cambridge University Press, Cambridge, 2019. A non-asymptotic viewpoint. MR 3967104, DOI 10.1017/9781108627771
- Stephen Warshall, A theorem on boolean matrices, J. Assoc. Comput. Mach. 9 (1962), 11–12. MR 149688, DOI 10.1145/321105.321107
- Neil White (ed.), Theory of matroids, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge University Press, Cambridge, 1986. MR 849389, DOI 10.1017/CBO9780511629563
- Neil White (ed.), Combinatorial geometries, Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge University Press, Cambridge, 1987. MR 921064, DOI 10.1017/CBO9781107325715
- Neil White (ed.), Matroid applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge University Press, Cambridge, 1992. MR 1165537, DOI 10.1017/CBO9780511662041
- Avi Wigderson, P, NP and mathematics—a computational complexity perspective, International Congress of Mathematicians. Vol. I, Eur. Math. Soc., Zürich, 2007, pp. 665–712. MR 2334207, DOI 10.4171/022-1/25
- Ryan Williams, Faster all-pairs shortest paths via circuit complexity, STOC’14—Proceedings of the 2014 ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 664–673. MR 3238994
- Gerhard J. Woeginger, The $\PP$-versus-$\NP$ page, https://www.win.tue.nl/~gwoegi/P-versus-NP.htm, retrieved 02 Feb 2021.
- Josephine Yu and Debbie S. Yuster, Representing tropical linear spaces by circuits, Formal Power Series and Algebraic Combinatorics, 2007, http://igm.univ-mlv.fr/~fpsac/FPSAC07/SITE07/PDF-Proceedings/Talks/78.pdf.
- H. Peyton Young and Shmuel Zamir (eds.), Handbook of game theory. Vol. 4, Handbooks in Economics, Elsevier/North-Holland, Amsterdam, 2015. MR 3752664
- Ruriko Yoshida, Leon Zhang, and Xu Zhang, Tropical principal component analysis and its application to phylogenetics, Bull. Math. Biol. 81 (2019), no. 2, 568–597. MR 3902912, DOI 10.1007/s11538-018-0493-4
- Leon Zhang, Computing min-convex hulls in the affine building of $\textrm {SL}_d$, Discrete Comput. Geom. 65 (2021), no. 4, 1314–1336. MR 4249906, DOI 10.1007/s00454-020-00223-x
- Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1
- Karel Zimmermann, A general separation theorem in extremal algebras, Ekonom.-Mat. Obzor 13 (1977), no. 2, 179–201 (English, with Czech summary). MR 453607
- Rade T. Zivaljevič, Topological methods in discrete geometry, Handbook of Discrete and Computational Geometry (Csaba D. Tóth, Jacob E. Goodmann, and Joseph O’Rourke, eds.), 3rd ed., CRC Press, Boca Raton, FL, 2018.
- Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim, Tropical geometry of deep neural networks, Proceedings of the 35th International Conference on Machine Learning (Jennifer Dy and Andreas Krause, eds.), Proceedings of Machine Learning Research, vol. 80, PMLR, 10–15 Jul 2018, pp. 5824–5832.
- Chuanming Zong, The cube: a window to convex and discrete geometry, Cambridge Tracts in Mathematics, vol. 168, Cambridge University Press, Cambridge, 2006. MR 2221660, DOI 10.1017/CBO9780511543173