Tropical Combinatorics and Applications

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This project aims at fundamental development of tropical combinatorics as well as its applications. Combinatorics is the art and science of distilling a complex mathematical structure into simple attributes and developing from this a deeper understanding of the original structure. Tropical mathematics, named after Brazilian mathematician Imre Simon of Sao Paulo on the Tropic of Capricorn, is a young area of mathematics arising from a number system with a pair operations: addition and maximum, instead of the more traditional pair of addition and multiplication. Tropical mathematics has applications in a wide range of areas including mirror symmetry, computational algebra, optimization, statistics, phylogenetics, and economics. The solutions of algebraic equations and inequalities are the main objects of interest in algebraic geometry; likewise the solutions of tropical algebraic equations and inequalities are the main players in tropical geometry. There is a precise relationship between algebro-geometric objects and their tropical counterparts, so tropical mathematics provides new insights into classical problems as well. It also provides a natural language and a new perspective for understanding deep and sometimes surprising connections between different mathematical entities. This project will make contributions to the foundation of tropical geometry, focusing on the combinatorial structures. The main geometric objects of study in this field are tropically convex sets and tropical algebraic sets, which can be constructed analogously to the usual convex sets and algebraic sets, but using the max-plus algebra. The investigator will study relationships between various combinatorial structures associated to an algebraic set, namely, its tropical variety, its algebraic matroid, and its Chow polytope. She will develop Ehrhart theory for enumeration of lattice points in tropical polytopes. In the other direction, the investigator will use tropical point of view to study classical objects in combinatorics and convex geometry. She will continue developing an approach to polytopes and triangulations based on tropical geometry and will investigate the relationship between the cone of positive semidefinite matrices and affine buildings. On the computational front, new algorithms for computing tropical varieties will be developed using numerical algebraic geometry, which has become one of the most powerful tools in algebraic geometry due to its highly parallelizable nature and advancements in numerical computations. These new methods will be useful for problems concerning polynomial systems which are ubiquitous in mathematical models in science and engineering. Specific applications include finding competitive equilibrium prices in product-mix auctions and discovering causal relationships between random variables in probability.