Skip to main content
Open Access Publications from the University of California

Combinatorics and Computations in Tropical Mathematics

  • Author(s): Lin, Bo
  • Advisor(s): Sturmfels, Bernd
  • et al.

In recent decades, tropical mathematics gradually evolved as a field of study in mathematics and it has more and more interactions with other fields and applications. In this thesis we solve combinatorial and computational problems concerning implicitization, linear systems and phylogenetic trees using tools and results from tropical mathematics.

In Chapter 1 we briefly introduce basic aspects of tropical mathematics, including tropical arithmetic, tropical polynomials and varieties, and the relationship between tropical geometry and phylogenetic trees.

In Chapter 2 we solve the implicitization problem for almost-toric hypersurfaces using results from tropical geometry. With results about the tropicalization of varieties, we present and prove a formula for the Newton polytopes of almost-toric hypersurfaces. This leads to a linear algebra approach for solving the implicitization problem. We implement our algorithm and show that it has better solving ability than some existing methods.

In Chapter 3 we compute linear systems on metric graphs. In algebraic geometry, linear systems on curves have been well-studied in the literature. In comparison, linear systems on metric graphs are their counterparts in tropical mathematics. We introduce the anchor divisors and anchor cells in order to compute the polyhedral cell complex structure of the linear system |D| and the tropical semi-module R(D). We develop algorithms, discuss their efficiency and present computational results for canonical linear systems on metric graphs.

In Chapter 4 we extend the previous chapter by introducing the tropical Hodge bundle, which is the counterpart of the Hodge bundle in tropical geometry. We study properties of tropical Hodge bundles and present computational results for some examples.

In Chapter 5 we study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all ultrametrics. The CAT(0)-metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the Owen-Provan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric exhibit properties that are desirable for geometric statistics, such as geodesics of small depth.

In Chapter 6 we study the Fermat-Weber points under the tropical metric. This is motivated by its application to the space of equidistant phylogenetic trees, here realized as the tropical linear space of all ultrametrics. While the Fréchet mean with the CAT(0)-metric of Billera-Holmes-Vogtman has been studied by many authors, the Fermat-Weber point under the tropical metric in tree spaces is not well understood. We investigate Fermat-Weber points under the tropical metric and we show that the set of tropical Fermat-Weber points for a given configuration is a classical convex polytope. We identify conditions under which this polytope is a point.

Main Content
Current View