Math 390C - Tropical Mathematics: Theory, Applications and Open Problems
Course description : Tropical mathematics is the interface of matroid theory, combinatorial optimization and algebraic geometry. It has found numerous applications in auction theory, mechanism design, game theory, complexity theory, discrete convex analysis. In particular, tropical geometry is a variational version of combinatorial optimization, where it examines the combinatorics and geometry of the entire space of input parameters, as opposed to analyzing the solution of a particular instance. It is an excellent tool for constructing examples and counter-examples in economics, game theory, network optimization, matroid theory and algebraic geometry.
This course aims to take students to the latest open research questions as fast as possible. After a set of introductory lectures, the majority of class time will be spent doing survey papers and literature review of existing research directions and student presentations on progress to open problems.
Lectures: Tuesday Thursday, 12.30 PM to 2.00 PM, RLM 11.176
Instructor: Ngoc Tran
Office hours: Tuesday Thursday, 11.30 AM to 12.30 PM, RLM 11.124
Prerequisites: graduate students in mathematics, electrical engineering, or consent of instructor
Grading policy: final grade = 3 homework sets x 20% + 1 final project report x 20% + 1 final project presentation x 20%
Final project format: the class breaks up to independent topics. On each topic, I will give a set of core lectures, and list a bunch of open problems. Students will choose at least one topic to dwelve further upon. On this topic, they need to either write a survey or work on a specific open problem (could be of their own suggestion, or an extension of a homework problem). Afterwards, they will present progress to the class.
Here is a tentative list of topics to be covered. The order of which they are presented are subjected to change.
Each topic ends with modern applications of tropical mathematics in fields including statistics, max-linear graphical models, phylogenetics, network theory, mechanism design, auction theory, game theory, complexity theory.
- Weeks 1-3: the `tropical' origin: tropical semigroup of matrices, max-plus linear systems and applications in queueing theory
- Weeks 4-8: Tropical combinatorics: linear spaces, oriented matroids, tropical varieties, learning tropical manifolds.
- Weeks 9-10: Discrete optimization and tropical geometry
- Weeks 11-12: student presentations
List of references.
Course materials, readings and project papers are drawn from the follow resources, to be continually updated.
- Synchronization and Linearity: An Algebra for Discrete Event Systems, Francois Baccelli, Guy Cohen, Geert Jan Olsder and Jean-Pierre Quadrat
- Max-linear Systems: Theory and Algorithms, Peter Butkovic
- Large deviations and idempotent probability, Anatolli Puhalskii
- Idempotent Analysis and Its Applications, Vassili N. Kolokoltsov and Victor P. Maslov
- Introduction to Tropical Geometry, Diane Maclagan and Bernd Sturmfels
- Essentials of Tropical Combinatorics, Michael Joswig
- Discrete convex analysis, Kazuo Murota
- Methods and Applications of (max,+) Linear Algebra, Marianne Akian, Guy Cohen, Stephane Gaubert, Jean-Pierre Quadrat and Michel Viot
- M. Akian, S. Gaubert, and A. Guterman. Tropical polyhedra are equivalent to mean payoff games
- X. Allamigeon, P. Benchimol, S. Gaubert, M. Joswig, Log-barrier interior point methods are not strongly polynomial
- X. Allamigeon, U. Fahrenberg, S. Gaubert, R. Katz and A. Legay, Tropical Fourier-Motzkin elimination, with an application to real-time verification
- J. Depersin, S. Gaubert, and M. Joswig. A tropical isoperimetric inequality
- Develin, Mike, and Bernd Sturmfels. Tropical convexity.
- Tropical hyperplane arrangements and oriented matroids
Federico Ardila, Mike Develin
- A Topological Representation Theorem for tropical oriented matroids, S Horn
- Valuations for matroid polytope subdivisions, F Ardila, A Fink, F Rincon
- Stiefel tropical linear spaces,
A Fink, F Rincon
- Monomial tropical cones for multicriteria optimization
Michael Joswig, Georg Loho
- Algorithms for tight spans and tropical linear spaces, Simon Hampe,
MichaelJoswig, Benjamin Schroeter
- Tropical linear spaces, David Speyer
- Tropical and ordinary convexity combined,
M Joswig, K Kulas
- Enumerating polytropes, N M Tran
- HodgeRank Is the Limit of Perron Rank, N M Tran
- Tropical Principal Component Analysis and its Application to Phylogenetics, Ruriko Yoshida, Leon Zhang, Xu Zhang
- Tropical Gaussians: A brief survey, Ngoc Tran
- Tropical geometry and mechanism design, R Crowell and N Tran
- Product-Mix Auctions and Tropical Geometry,
Ngoc Mai Tran, Josephine Yu
- Split probabilities and species tree inference under the multispecies coalescent model, E.S. Allman, J.H. Degnan and J.A. Rhodes
- L. Zhang, G. Naitzat, and L.-H. Lim, "Tropical geometry of deep neural networks"
- Bayesian Networks for Max-linear Models,
Claudia Klueppelberg, Steffen Lauritzen
- Maximum Likelihood Estimation for Totally Positive Log-Concave Densities
Elina Robeva, Bernd Sturmfels, Ngoc Tran, Caroline Uhler
- Tropical matrix duality and Green's D relation
Christopher Hollings, Mark Kambites
Identities in Upper Triangular Tropical Matrix Semigroups and the Bicyclic Monoid, Laure Daviaud, Marianne Johnson, Mark Kambites
- Geometry and algorithms for upper triangular tropical matrix identities, Marianne Johnson, Ngoc Mai Tran
- Performance Evaluation of (max,+) Automata, Stephane Gaubert
- Valuated matroids, Andreas W.M Dress, Walter Wenzel
- Valuated matroids: a new look at the greedy algorithm, Andreas W.M.Dress, Walter Wenzel
Please take note of the add/drop deadlines here at the university calendar. There are no provisions to adjust scores due to late enrolment.
Make-ups for homeworks
No late homework or final projects will be accepted.
Should you have serious medical problem or genuine emergency, please obtain a written or electronic letter from the Student Emergency Serivces. Under exceptional circumstances, I will give partial grade, provided you have a C average on previous coursework.
Services for students with disabilities
The University of Texas at Austin provides upon request
appropriate academic accommodations for qualified stu-
dents with disabilities. For more information, contact
Services for Students with Disabilities at 471-6259
(voice) or 232-2937 (video phone)
being enrolled in the class, you have agreed to adhere to the student honor code and the university code of conduct. Violations will be treated as required the university policy.