🌴Tropical Geometry Unit 3 – Tropical Convexity and Polyhedra

Key Concepts and Definitions

• Tropical geometry studies geometric objects defined by tropical algebra operations (addition and multiplication)
• Tropical convexity extends classical convexity to the tropical setting using max-plus algebra
• Tropical polyhedra are analogous to classical polyhedra but defined using tropical halfspaces and hyperplanes
  • Tropical halfspaces are regions of the form $\{x \in \mathbb{R}^n : a_1 \odot x_1 \oplus \cdots \oplus a_n \odot x_n \leq b\}$
  • Tropical hyperplanes are regions of the form $\{x \in \mathbb{R}^n : a_1 \odot x_1 \oplus \cdots \oplus a_n \odot x_n = b\}$
• Idempotent semirings generalize tropical algebra by satisfying idempotency property ($a \oplus a = a$)
• Tropical projective torus $\mathbb{TP}^{n-1}$ is the quotient of $\mathbb{R}^n$ by tropical scalar multiplication
• Tropical convex hull of a set $S \subseteq \mathbb{R}^n$ is the smallest tropically convex set containing $S$

Tropical Algebra Basics

• Tropical addition $\oplus$ is defined as the maximum operation ($a \oplus b = \max\{a, b\}$)
• Tropical multiplication $\odot$ is defined as the usual addition ($a \odot b = a + b$)
• Tropical division $\oslash$ is defined as the usual subtraction ($a \oslash b = a - b$)
• Tropical powers are defined using repeated tropical multiplication ($a^{\odot n} = na$)
• Tropical algebra satisfies most axioms of a semiring except for the additive inverse
  • Additive identity is $-\infty$ and multiplicative identity is $0$
• Tropical polynomial functions are piecewise linear and convex
  • Example: $f(x) = 2 \odot x^{\odot 2} \oplus 1 \odot x \oplus 3 = \max\{2 + 2x, 1 + x, 3\}$

Tropical Convexity Fundamentals

• A set $C \subseteq \mathbb{R}^n$ is tropically convex if it contains the tropical line segment between any two points
  • Tropical line segment: $\{a \odot x \oplus b \odot y : a \oplus b = 0\}$ for $x, y \in C$
• Tropical convex sets are closed under tropical addition and tropical scalar multiplication
• Tropical convex hull $\operatorname{tconv}(S)$ is the intersection of all tropically convex sets containing $S$
  • Can be constructed using tropical line segments and tropical scalar multiplication
• Tropical convex sets have a unique minimal generating set called the tropical extreme points
• Separation theorem holds in tropical setting: disjoint tropically convex sets can be separated by a tropical hyperplane
• Tropical cyclic polytopes are important examples of tropical polytopes with interesting combinatorial properties

Tropical Polyhedra and Their Properties

• Tropical polyhedra are intersections of finitely many tropical halfspaces
  • Defined by a system of tropical linear inequalities $A \odot x \leq b$
• Bounded tropical polyhedra are called tropical polytopes
• Tropical polyhedra are tropically convex and closed under tropical scalar multiplication
• Tropical vertices are points that cannot be expressed as the tropical convex combination of other points
  • Correspond to the extreme points of the tropical polyhedron
• Tropical edges are line segments connecting two tropical vertices
• Tropical faces are intersections of the polyhedron with tropical hyperplanes that contain it
  • Tropical faces form a lattice ordered by inclusion
• Tropical Minkowski sum of two polyhedra $P \oplus Q$ is the tropical convex hull of the sum of their points
  • Tropical Minkowski sum of polytopes is a polytope

Geometric Representations

• Tropical polyhedra can be represented as the projection of a higher-dimensional classical polyhedron
  • Allows the use of classical polyhedral geometry techniques
• Tropical moment map associates a tropical polytope to a classical polytope
  • Useful for studying the combinatorial structure of tropical polytopes
• Regular subdivisions of Newton polytopes correspond to tropical hypersurfaces
  • Provides a connection between tropical geometry and algebraic geometry
• Tropical Grassmannians parametrize tropicalizations of linear spaces
  • Important in the study of tropical Plücker vectors and tropical determinants
• Tropical curves and tropical surfaces can be represented using Newton polygons and Newton polytopes
  • Helps in understanding the combinatorial structure and singularities

Applications in Optimization

• Tropical linear programming optimizes a tropical linear objective function over a tropical polyhedron
  • Reduces to solving a system of tropical linear equations and inequalities
• Tropical convex hull computation is used in solving tropical optimization problems
  • Algorithms include tropical double description method and tropical beneath-beyond method
• Tropical support vector machines (SVM) use tropical convexity for classification tasks
  • Separates data points using tropical hyperplanes in feature space
• Tropical principal component analysis (PCA) finds tropical principal components maximizing the tropical variance
  • Used for dimensionality reduction and data visualization in tropical setting
• Tropical optimal transport problems study the transportation of mass between tropical probability measures
  • Involves solving tropical Kantorovich-Rubinstein duality and tropical Wasserstein distances

Computational Techniques

• Tropical Fourier-Motzkin elimination eliminates variables from a system of tropical linear inequalities
  • Analogous to classical Fourier-Motzkin elimination in linear programming
• Tropical vertex enumeration algorithms compute the vertices of a tropical polyhedron
  • Examples include tropical double description method and tropical beneath-beyond method
• Tropical halfspace intersection algorithms construct tropical polyhedra as intersections of halfspaces
  • Incremental algorithm adds one halfspace at a time and updates the polyhedron
• Tropical convex hull algorithms compute the tropical convex hull of a set of points
  • Includes tropical quickhull algorithm and tropical beneath-beyond method
• Tropical linear programming solvers use techniques like tropical simplex method and tropical interior point methods
  • Exploit the piecewise linear structure of tropical objective functions and constraints

Advanced Topics and Current Research

• Tropical semidefinite programming extends semidefinite programming to the tropical setting
  • Studies optimization problems over the cone of tropical positive semidefinite matrices
• Tropical integer programming investigates optimization problems with tropical linear constraints and integer variables
  • Involves studying tropical Hilbert bases and tropical Graver bases
• Tropical game theory models strategic interactions using tropical algebra
  • Tropical Nash equilibria and tropical minimax theorems are important concepts
• Tropical persistent homology applies persistent homology to data with tropical structure
  • Used for topological data analysis in the tropical setting
• Tropical algebraic statistics combines tropical geometry with algebraic statistics
  • Studies statistical models defined by tropical polynomials and their inference
• Tropical optimization in phylogenetics reconstructs phylogenetic trees using tropical distances
  • Involves solving tropical Fermat-Weber problem and tropical Steiner tree problem