Essentials of Tropical Combinatorics

Joswig, Michael

doi:10.1090/gsm/219

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

ePUB View full volume as ePUB

PDF View full volume as PDF

Read more about this volume

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

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

Table of Contents

References [Enhancements On Off] (What's this?)