MIT Combinatorics Seminar

Combinatorial Aspects of Tropical Geometry

Thorsten Theobald (TU Berlin and Yale University)

Tropical geometry is the geometry of the tropical semiring $(\mathbb{R}, \min, +)$. Tropical varieties are polyhedral cell complexes which behave like complex algebraic varieties. The link between classical complex geometry and tropical geometry is provided by amoebas, which are logarithmic images of complex varieties.

In this talk, we begin with a combinatorially oriented review of some fundamental concepts in tropical geometry (aimed at a general audience), and then we turn towards some algorithmic problems concerning the intersection of tropical hypersurfaces in general dimension: deciding whether this intersection is nonempty, whether it is a tropical variety, and whether it is connected, as well as counting the number of connected components. We characterize the borderline between tractable and hard computations by proving NP-hardness and #P-hardness results even under various strong restrictions of the input data, as well as providing polynomial time