Tropical Combinatorics

Tropical mathematics arises from the max-plus semifield. The max-plus algebra, especially max-plus linear algebra and applications to computer science, combinatorics, and optimization, have been studied since 1970s by Cuninghame-Green, Kleene, Zimmermann, and others. However, much of the development in tropical geometry in the last 20 years is due to the tropicalization process, which turns algebro-geometric objects into combinatorial ones.

Tropicalization of algebraic sets, also known as Maslov dequantization or logarithmic limit sets, was introduced by Bergman to study the “exponential behavior at infinity” of algebraic varieties, by Viro to construct real plane curves with prescribed degree and topology, by Mikhalkin to count algebraic curves, and by Sturmfels for solving systems of polynomial equations.

Tropicalization has led to numerous recent breakthroughs in diverse areas of mathematics such as topology of moduli spaces of curves Cha21 and optimization ABGJ21. Moreover, tropicalization gives us constructions, intuition, and analogies for studying purely combinatorial objects as well, even if they do not arise as shadows of algebraic geometry. This is the case, for example, in the development of combinatorial Hodge theory, which contributed in great part to the recent Fields medal award given to June Huh.

In this article we introduce some of the basic constructions in tropical geometry, focusing on linear spaces and Grassmannians for their combinatorial significance. We give pointers to some recent research frontiers and discuss applications in matroid theory, phylogenetic trees, and auction theory.

In Section 1 we provide background on tropicalization of algebraic sets. In Section 2 we discuss tropicalizations of linear subspaces, their connection to matroids, and tropicalizations of Grassmannians, which are parameter spaces for the set of all linear subspaces of a fixed dimension in an ambient vector space. In Section 3, we look beyond the tropical Grassmannian and study the Dressian as a parameter space of all valuated matroids, not just those arising from linear subspaces. The Dressian provides a unifying language for applications in economics, which we discuss in Section 4.

1. Tropical Foundations

In this section we explain how tropicalization uncovers combinatorial structure of algebraic objects, such as Newton polytopes of polynomials and their subdivisions. More generally, we discuss how tropicalizations of algebraic sets are piecewise linear objects with rich combinatorial structure. We refer to the book MS15 for proofs and more details.

Tropical or max-plus algebra is algebra over the real numbers $\mathbb{R}$ with tropical addition

$$\begin{equation*} a \oplus b = \max (a,b) \end{equation*}$$

and tropical multiplication

$$\begin{equation*} a \odot b = a + b. \end{equation*}$$

The operations satisfy associative, commutative, and distributive laws. The multiplicative identity is $0$. We may optionally adjoin $-\infty$ if we desire an additive identity, but there are no additive inverses.

Tropical operations arise from limits of logarithms. To build intuition, consider two monic polynomials $F,G \in \mathbb{R}[x]$. If $x$ is very large, then $F,G$ are each dominated by the monomial of highest degree, so $F(x) \sim x^a$, $G(x) \sim x^b$ for some $a,b > 0$. Then, $(F \cdot G)(x) \sim x^{a+b}$, and if $a \neq b$, then $(F+G)(x) \sim x^{\max (a,b)}$. In other words, if we work with large values of $x$, then multiplication and addition of polynomials corresponds to addition and taking maxima of exponents. Let us now consider a richer variant of the above. A non-Archimedean valuation on a field $\mathbb{K}$ is a map $\nu : \mathbb{K}\setminus \{0\} \rightarrow \mathbb{R}$ satisfying

1.

$\nu (ab) = \nu (a) \odot \nu (b)$

2.

$-\nu (a+b) \leq -\nu (a) \oplus -\nu (b)$.

For example, $\mathbb{K}$ can be the field $\mathbb{C}((t))$ of Laurent series with complex coefficients, which are formal power series where exponents can start at a negative integer, or its algebraic closure, the field of Puiseux series $\bigcup _{n \geq 1}\mathbb{C}((t^{\frac{1}{n}}))$. Then a valuation could be the lowest exponent of a term with nonzero coefficient.

We now have two different ways to tropicalize. We can tropicalize a polynomial over $\mathbb{K}$ by replacing the algebraic operations with tropical operations, and replacing the coefficients with (negative of) their valuations. On the other hand, we can tropicalize a subset of $(\mathbb{K}\setminus \{0\})^n$ by taking (negative of) valuations coordinate-wise. For example, consider the univariate polynomial

$$F(x) = x^3 - (t^{-4} + t^{-3} + t^{-2}) x + (t^{-5} + t^{-4})$$

with coefficients in the field of Laurent series $\mathbb{C}((t))$. The three roots of $F$ are the Laurent series $t^{-2}$, $-t^{-2} - t^{-1}$, and $t^{-1}$. We can tropicalize $F(x)$ to obtain the polynomial

$$\begin{equation} f(x) = \operatorname {trop}(F(x)) = 0 \odot x^{\odot 3} \oplus 4 \odot x \oplus 5. {\tag{1}} \end{equation}$$

We can also take (negative of) valuations of the three roots, obtaining the real numbers $2$, $2$, and $1$. These two ways of tropicalizing are compatible, if we define roots of tropical polynomials appropriately. This is the content of the Fundamental Theorem of Tropical Algebraic Geometry, which we will now work towards.

Defining the roots of a tropical polynomial $f$ by “solving” for $f = 0$ or $f = -\infty$ is not a very useful notion, due to the fact that tropical algebra has no additive inverses. However, there are still good ways to define tropical roots, and more generally, tropical hypersurfaces, varieties, and their algebraic companions, ideals.

To motivate the definitions, consider the tropical polynomial $f$ from Equation 1 above.

Figure 1.

The graph of the tropical polynomial $f$ defined in 1. Each tropical monomial is a usual affine function, and the tropical polynomial is the maximum of affine functions. The tropical roots of $f$ are $1$ and $2$, which are the values of $x$ where the graph bends.

We could try to factor $f$ into linear factors to define its roots. This is not possible, though, as the degree-$2$ terms cannot be canceled out in a tropical product of lower-degree polynomials. Nonetheless, as real functions, we have the equality

$$\begin{equation} f(x) \equiv (x \oplus 2) \odot (x \oplus 2) \odot (x \oplus 1). {\tag{2}} \end{equation}$$

Tropically multiplying a function by the linear polynomial $(x \oplus a)$ translates its graph vertically by $a$ units and then bends the graph up by slope one for $x \geq a$. This means that the factorization is determined by where the slopes change in the graph of $f$. Thus 2 is the unique factorization of $f$ into monic linear factors, which motivates us to say that the tropical roots of $f$ are $2$ and $1$, with $2$ being a root of multiplicity two. These are exactly the values of $x$ where the maximum (tropical sum) is attained by at least two of the three tropical monomial terms that make up the tropical polynomial $f$ in the expression 1. The three tropical monomials are usual linear functions, shown by the lines in Figure 1. Note that the three tropical roots are also the valuations of the three roots of the original polynomial $F(x)$. More generally, we have the following.

Definition 1.1.

The tropical hypersurface $\mathcal{V}^{\operatorname {trop}}(f)$ of a tropical polynomial $f$ in $n$ variables is defined as the locus of points $\mathbf{x}\in \mathbb{R}^n$ for which the maximum is attained at least twice among the tropical monomial terms of $f(\mathbf{x})$. Equivalently, it is the corner locus of the piecewise linear function $f$.

Let $\mathbb{K}$ be a field with a nontrivial non-Archimedean valuation $\nu$. The tropicalization of a polynomial over $\mathbb{K}$ is obtained by replacing addition and multiplication with their tropical counterparts and replacing the coefficients with minus their valuations. The tropicalization of a point $\mathbf{x}= (x_1,\dots ,x_n) \in \mathbb{K}^n$ is

$$\begin{equation*} \operatorname {trop}(\mathbf{x}) = (-\nu (x_1),\dots ,-\nu (x_n)). \end{equation*}$$

For a subset $S \subset \mathbb{K}^n$, we can define its tropicalization as

$$\begin{equation*} \operatorname {trop}(S) = \overline{\{\operatorname {trop}(\mathbf{x}) \mid \mathbf{x}\in S\}}, \end{equation*}$$

where the bar on the right-hand side denotes the closure in the Euclidean topology.

Thus, from a polynomial $F \in \mathbb{K}[\mathbf{x}]$ we get two tropical objects: the tropicalization of $F$, and the tropicalization of its zero locus in $\mathbb{K}^n$. The following theorem of Kapranov says that this latter set is precisely the set of tropical roots of $\operatorname {trop}(F)$.

Theorem 1.2 (Kapranov, 1990s).

For any polynomial $F$ we have

$$\begin{equation*} \mathcal{V}^{\operatorname {trop}} (\operatorname {trop}(F) ) = \overline{ \{\operatorname {trop}(\mathbf{x}) \mid \mathbf{x}\in \mathbb{K}^n, F(\mathbf{x}) = 0\} } \end{equation*}$$

where $\mathbb{K}$ is an algebraically closed extension of the field of definition of $F$ with a nontrivial non-Archimedean valuation, and the closure is taken in the Euclidean topology of $\mathbb{R}^n$.

What information about the tropical polynomial $f$ does the tropical hypersurface $\mathcal{V}^{\operatorname {trop}}(f)$ retain? Written using regular arithmetic, a tropical polynomial $f$ in $n$ variables $x_1,\dots ,x_n$ is a function of the form

$$\begin{equation*} f = \max _{\mathbf{a}\in A} (c_\mathbf{a}+ \mathbf{x}\cdot \mathbf{a}) = \max _{\mathbf{a}\in A} \left((\mathbf{x},1) \cdot (\mathbf{a}, c_\mathbf{a})\right) \end{equation*}$$

where $\mathbf{x}= (x_1,\dots ,x_n)$. The set $A \subset \mathbb{Z}^n$ consists of the exponents of monomials appearing in $f$ and is called the support of $f$. The coefficients $c_\mathbf{a}$ are real numbers.

We can think of the point $(\mathbf{a}, c_\mathbf{a}) \in \mathbb{R}^{n+1}$ as the point $\mathbf{a}\in \mathbb{R}^n$ lifted to height $c_\mathbf{a}$ in a new dimension. Then $f$ is the function that sends $\mathbf{x}\in \mathbb{R}^n$ to the maximum dot product of $(\mathbf{x},1)$ with the lifted points $(\mathbf{a}, c_\mathbf{a})$ for $\mathbf{a}\in A$. The tropical hypersurface $\mathcal{V}^{\operatorname {trop}}(f)$ consists of all the points $\mathbf{x}$ where this maximum is attained at least twice.

Convex geometry tells us that, when maximizing a linear function on a set, the possible locations of the points achieving the maxima are the faces of the convex hull of the set. When maximizing the dot product with vectors of the form $(\mathbf{x}, 1)$ on the lifted points $(\mathbf{a}, c_\mathbf{a})$, the maxima can only occur on the faces on the upper part of the convex hull, since these faces have an upward-pointing normal vector, i.e., an outer normal vector with positive last coordinate. See Figure 2 for an example of lifted points and their upper convex hulls.

This means that the tropical hypersurface $\mathcal{V}^{\operatorname {trop}}(f)$ is determined by the faces in the upper convex hull of the lifted points $(\mathbf{a}, c_\mathbf{a})$ with $\mathbf{a}\in A$. More concretely, if we take the upper convex hull of the lifted points and project its faces back down to $\mathbb{R}^n$, we obtain a decomposition of the Newton polytope of $f$, which is the convex hull of the support of $f$, as a union of smaller polytopes. This decomposition is called the regular subdivision of the Newton polytope of $f$ induced by the lift to heights given by the coefficients of $f$. The tropical hypersurface $\mathcal{V}^{\operatorname {trop}}(f)$ is a polyhedral complex whose faces or cells are in (inclusion-reversing) bijection with non-singleton faces of this regular subdivision. This statement is often referred to as the duality between tropical hypersurfaces and regular subdivisions. Compare Figures 2 and 3.

Example 1.3.

Figure 2.

Regular subdivisions of the unit square corresponding to the tropical polynomials $0 \oplus (1 \odot x) \oplus (1 \odot y) \oplus (1 \odot x \odot y)$ and $0 \oplus (1 \odot x) \oplus (1 \odot y) \oplus (3 \odot x \odot y)$. The gray dashed line shows the linear function $u(x,y) = x+y$, for reference.

Figure 3.

Tropical hypersurfaces of the tropical polynomials in Example 1.3. Compare the vertices in these figures with the normal vectors to the faces in the upper convex hulls in Figure 2.

Consider a tropical polynomial in two variables $x$ and $y$ of the form

$$f(x,y) =( u_{00} \odot 0 ) \oplus (u_{10} \odot x) \oplus (u_{01}\odot y) \oplus (u_{11}\odot x \odot y).$$

Its support is $\{(0,0), (1,0), (0,1), (1,1)\} \subset \mathbb{Z}^2$, and thus its Newton polytope is the unit square $[0,1]^2$. Its regular subdivision is obtained by lifting up the four corners of the square to the heights $u_{ij}$, taking the upper convex hull, and projecting back down to the square. If $u_{00} + u_{11} < u_{01} + u_{10}$, then we obtain the subdivision of the square into two triangles as shown on the left in Figure 2. If the inequality goes the other way, then we obtain the subdivision shown on the right. If there is equality, we obtain the full square unsubdivided.

These subdivisions turn up in auction theory of indivisible distinct goods. Here, the coefficient map $u: \{0,1\}^2 \to \mathbb{R}$ is called a bid function, with $u_{ij}$ representing how much a bidder is willing to pay for the goods bundle consisting of $i$ copies of goods 1 and $j$ copies of goods 2. The regular subdivision $\Delta _u$ represents the relationship between the two items: on the right of Figure 2, the two items are complements (such as milk and coffee), since together they are worth more to the bidder than the sum of their individual values. In other words, the bidder would strongly prefer having both milk and coffee, over having milk alone or coffee alone. In the other case, on the left, the two items are called substitutes (such as coffee and tea). Some open questions in auction theory were resolved using tropical geometry, by studying the combinatorial types of the bidders’ functions. We discuss this in Section 4.

We now consider the case of multiple polynomials. For a single polynomial, its Newton polytope is a natural polyhedral object carrying some discrete invariants such as the degree and the asymptotic behavior of the corresponding hypersurface. When we have a polynomial ideal instead of a single polynomial, what could an analogous polyhedral object be? Tropical geometry provides an answer.

If $I \subset \mathbb{K}[x_1, \dots , x_n]$ is an ideal with variety $V(I) = \{\mathbf{x}\in \mathbb{K}^n \mid F(\mathbf{x}) = 0 \text{ for all } F \in I\}$, we define its tropical variety as the tropicalization of $V(I)$:

$$\begin{equation*} \operatorname {trop}(V(I)) = \overline{\{\operatorname {trop}(\mathbf{x}) \mid \mathbf{x}\in V(I) \}}. \end{equation*}$$

The Fundamental Theorem of Tropical Algebraic Geometry generalizes Kapranov’s theorem to any ideal.

Theorem 1.4 (Fundamental Theorem of Tropical Algebraic Geometry).

Suppose $\mathbb{K}$ is an algebraically closed field with a nontrivial non-Archimedean valuation, and $I \subset \mathbb{K}[x_1,\dots ,x_n]$ is an ideal. Then

$$\begin{equation*} \operatorname {trop}(V(I)) = \bigcap _{F \in I}\mathcal{V}^{\operatorname {trop}{}}(\operatorname {trop}(F)). \end{equation*}$$

That is, the two ways of tropicalizing are compatible—taking (minus) the valuations of points in the variety $V(I)$, and intersecting the tropical hypersurfaces of the tropicalizations of all polynomials in the ideal $I$. This intersection can in fact be taken to be finite, and a finite subset of $I$ that suffices is called a tropical basis—every ideal in a polynomial ring has a tropical basis. There are other ways of describing the tropicalization of an algebraic variety, using logarithmic limits, Gröbner theory, or Berkovich analytifications.

What kind of objects are tropical varieties? Although not immediate from the definition, tropicalizations of algebraic varieties are polyhedral or piecewise linear objects. This was known since Bergman’s work and is equivalent to the existence of tropical bases. Bieri and Groves showed in 1984 that the tropicalization has the same dimension as the original variety. Moreover, the Structure Theorem of Tropical Geometry says that the tropicalization of an irreducible variety is connected through codimension-one faces and that it satisfies a balancing condition. In Figure 3, the balancing condition means that, locally around every vertex, the outgoing direction vectors sum to zero, if weighted appropriately. The balancing condition is a generalization of this statement to higher dimensions. Connectedness through codimension-one faces means that the polyhedral object remains connected even after removing all codimension-two faces.

The connectedness part of the Structure Theorem was recently strengthened—the tropicalization of a $d$-dimensional irreducible variety is connected through codimension-one faces even after removing any $d-1$ pointed maximal faces from it GHM$^{+}$21. This provides a new tool for the realizability problem of determining whether a given polyhedral object arises as the tropicalization of an irreducible algebraic variety.

2. Tropicalized Linear Spaces and Grassmannians

Linear subspaces are some of the simplest algebraic varieties. It turns out that their tropicalizations are quite rich, with an interesting connection to phylogenetic trees. We now take a quick tour into this world.

A tropical hyperplane in $\mathbb{R}^d$ is the tropical variety of a tropical linear function $f = \bigoplus _{i=1}^d a_i \odot x_i$. However, it is not so obvious what the notion of a more general tropical linear space should be. Classically, there are many equivalent characterizations of linear subspaces: as the linear span of a set of vectors, as an intersection of hyperplanes, and as a nonempty subset that is closed under linear combinations, to name a few. However, the absence of additive inverses makes these notions quite different in tropical geometry. As it turns out, the right notion of tropical linear space arises when considering the Plücker embedding of Grassmann variety.

In the 19th century, Julius Plücker realized that the set of planes in $4$-dimensional affine space $\mathbb{K}^4$ can be nicely parametrized by a quadratic subvariety of $\mathbb{P}^5$. His work was later generalized by Hermann Grassmann, who found a way of parametrizing all subspaces of $\mathbb{K}^n$ of a fixed dimension $d$ by a projective variety that we now know as the Grassmannian.

Concretely, any $d$-dimensional subspace $L$ of $\mathbb{K}^n$ can be written as the row space of a $d\times n$ matrix $A$. The Plücker coordinates of $L$ are the $\binom{n}{d}$ maximal minors of $A$, and they form a point in $\mathbb{P}^{\binom{n}{d}-1}$. These Plücker coordinates depend only on the subspace $L$ and not on the chosen matrix $A$, since row operations on the matrix $A$ only change its maximal minors by a global scalar multiple. The Grassmannian $\operatorname {Gr}(d,n)$ is the subvariety of $\mathbb{P}^{\binom{n}{d}-1}$ consisting of the Plücker coordinates of all $d$-dimensional subspaces of $\mathbb{K}^n$. Any linear subspace $L$ is completely determined by its vector of Plücker coordinates, and thus the Grassmann variety $\operatorname {Gr}(d,n)$ serves as the parameter space for all $d$-dimensional subspaces of $\mathbb{K}^n$.

The Grassmannian $\operatorname {Gr}(d,n)$ is a variety of dimension $d(n-d)$—much lower than that of its ambient projective space, $\mathbb{P}^{\binom{n}{d}-1}$. This variety is defined by polynomials known as the Plücker relations. For example, $\operatorname {Gr}(2,4)$ is defined by the unique quadratic relation satisfied among the six maximal minors of a $2 \times 4$ matrix:

$$\begin{equation} p_{12} p_{34} - p_{13} p_{24} + p_{14}p_{23} = 0, {\tag{3}} \end{equation}$$

where $p_{ij}$ denotes the maximal minor corresponding to the submatrix consisting of columns $i$ and $j$.

This correspondence between linear subspaces and points in the Grassmannian turns out to carry on into the tropical world. For simplicity, let us fix a valued field with a surjective non-Archimedean valuation onto $\mathbb{R}$. Under this setup, tropicalizing the Grassmann variety $\operatorname {Gr}(d,n)$ under its Plücker embedding in $\mathbb{P}^{\binom{n}{d}-1}$ produces a tropical variety whose points parametrize the set of tropicalizations of all $d$-dimensional subspaces of $\mathbb{K}^n$. In other words, the tropicalization of a linear subspace of $\mathbb{K}^n$ is determined by—and also determines—the valuations of all its Plücker coordinates.

Theorem 2.1 (Speyer and Sturmfels, 2004).

The following diagram commutes, with the horizontal maps being one-to-one correspondences:

$$\begin{equation*} \vcenter{\img[][190pt][64pt][{$\xymatrix{ \Gr(d,n) \ar@{&lt;-&gt;}[r] \ar@{-&gt;&gt;}[d]_{\trop} &amp; \{ d \text{-dim subspaces of } \mathbb K^n \} \ar@{-&gt;&gt;}[d]^{\trop} \\ \trop(\Gr(d,n)) \ar@{&lt;-&gt;}[r] &amp; {\left\{ \begin{array}{l} d \text{-dim tropicalized} \\ \text{linear spaces in } \mathbb{R}^n \end{array} \right\}}. }$}]{Images/img02091a89c654dc80aea98d79b4bbaebc.svg}} \end{equation*}$$

The tropicalization of any $d$-dimensional linear subspace is a pure $d$-dimensional polyhedral complex that is balanced when assigned multiplicities equal to 1 to all its maximal cones. Furthermore, these polyhedral complexes are tropical varieties of degree 1: the number of points (counted with multiplicity) in their intersection with a generic tropical linear subspace of the complementary dimension is always equal to 1. However, as we will discuss in Section 3, the class of tropical varieties of degree $1$ consists of more than just tropicalizations of linear subspaces, and it is tightly connected to the study of (valuated) matroids.

Tropical Grassmannians and phylogenetics trees

A phylogenetic tree $T$ is a tree on $n$ labelled leaves $\{1,2,\dots ,n\}$ where the internal (non-leaf) edges are weighted by positive numbers and the leaf edges are weighted by real numbers. Such a tree $T$ produces a pairwise dissimilarity vector $d(2,T) = \{d_{ij}(T): 1 \leq i < j \leq n\} \in \mathbb{R}^{\binom{n}{2}}$ where $d_{ij}(T)$ is the sum of edge weights along the unique path from leaf $i$ to leaf $j$ in $T$. An arbitrary vector $d \in \mathbb{R}^{\binom{n}{2}}$ equals $d(2,T)$ for some tree $T$ if and only if it satisfies the four-point condition: for each set of four distinct points $\{i,j,k,\ell \} \subseteq [n]$, the tuple $(d_{ij}, d_{ik}, d_{i\ell }, d_{jk}, d_{j\ell }, d_{k\ell }) \in \mathbb{R}^6$ lies on the tropical variety cut out by the polynomial

$$\begin{equation} (d_{ij}\odot d_{k\ell }) \oplus (d_{ik}\odot d_{j\ell }) \oplus (d_{i\ell }\odot d_{jk}). {\tag{4}} \end{equation}$$

That is, the maximum among the above three terms is achieved at least twice. Note that 4 is the tropicalization of the quadratic Plücker relation 3! In general, we have the following theorem.

Theorem 2.2 (Pachter and Sturmfels, 2005; Speyer and Sturmfels, 2004).

The space of pairwise dissimilarity vectors of phylogenetic trees with $n$ leaves equals the tropical Grassmannian $\operatorname {trop}(\operatorname {Gr}(2,n))$.

Theorem 2.2 is at the heart of the tropical approach to phylogenetics. An important problem in phylogenetics is to infer the tree $T$ given noisy measurements of the dissimilarity vector $d(2,T)$. For example, suppose that from different data sets one can obtain dissimilarity vectors $d_1,\dots ,d_k$, each corresponding to a different phylogenetic tree $T_1,\dots ,T_k$ on the same $[n]$ leaves. One would like to aggregate the information across these trees, and output a single “best estimator” $\hat{T}$. Unfortunately, the mean of the dissimilarity vectors $\bar{d} = \frac{1}{k}\sum _{j=1}^k d_j$ may not be a dissimilarity vector itself. Instead, one could formulate an optimization problem over the space of trees to find a tree $\hat{T}$ that minimizes the “average distance” to the observed trees $d_1,\dots ,d_k$. Solving this optimization problem is an active research area, and the choice of metric on the tree space plays an important role. Here, the geometry of $\operatorname {trop}(\operatorname {Gr}(2,n))$ suggests that the tropical Hilbert metric is a natural choice MLYK18.

One major quest in theoretical applications of tropical geometry to phylogenetics was to generalize the Pachter–Sturmfels theorem to higher-order dissimilarity vectors, which assign a number to each $r$-subset of leaves of a phylogenetic tree $T$. Recently, it was shown in CGMS21 that for $2 \leq r \leq n-2$, the set of weighted $r$-order dissimilarity vectors of phylogenetic trees on $n$ leaves is the tropicalization of a natural subvariety of $\operatorname {trop}(\operatorname {Gr}(r,n))$, whose tropical basis generalizes the four-point condition 4.

3. Tropical Linear Spaces and Matroids

The tropicalization of the Grassmannian $\operatorname {Gr}(d,n)$ depends in general on the ground field. However, we still get a combinatorially meaningful space if we consider the set of points in $\mathbb{R}^{\binom{n}{d}}$ satisfying just the tropical quadratic Plücker relations, and not necessarily higher-degree relations among Plücker coordinates.

Definition 3.1.

The Dressian $\operatorname {Dr}(d,n)$ is the space of real-valued functions $p$ on $d$-element subsets of $\{1,2,\dots ,n\}$ satisfying the following tropical quadratic Plücker relations: for any $A,B \subset \{1,2,\dots ,n\}$ with $|A| = d-1$ and $|B| = d+1$, the maximum

$$\begin{equation} \max _{i \in B \setminus A} p(A \cup i) + p(B \setminus i) \text{ is achieved twice.} {\tag{5}} \end{equation}$$

For example, if $d = 2$ and $n=4$, then 5 is exactly the four-point condition 4, and the Dressian and the tropical Grassmannian coincide. However, in general the tropical Grassmannian is a proper lower-dimensional subset of the Dressian, as it is cut out by the tropicalizations of all relations among the maximal minors of a $d \times n$ matrix, not just the quadratic ones.

The tropical quadratic Plücker relations 5 encode the basis exchange axiom that defines valuated matroids, and thus the Dressian $\operatorname {Dr}(d,n)$ turns out to be exactly the space of valuated matroids of rank $d$ on the ground set $\{1,\dots ,n\}$. This section elaborates on this fundamental connection.

Matroids are combinatorial objects that abstract and generalize several notions of independence in mathematics such as linear independence among vectors in a vector space or algebraic independence among elements of field extension. If a $d$-dimensional linear space $L$ is the row span of a $d \times n$ matrix $A$, then a collection of $d$ columns of $A$ are linearly independent if and only if the corresponding Plücker coordinate of $L$ is nonzero. In other words, the matroid recording the linear dependencies among the coordinate functions on $L$ encodes the zero-pattern of the vector of Plücker coordinates of $L$.

Matroids have been studied extensively since their introduction by Whitney and Nakasawa in the 1930s, and have found tight connections to several areas such as graph theory, optimization, and coding theory. Valuated matroids are an elegant generalization of matroids introduced by Dress and Wenzel in 1992, in which every maximal independent set $B$ is assigned a valuation $p(B) \in \mathbb{R}$. For example, a $d \times n$ matrix of rank $d$ over a valued field $\mathbb{K}$ gives rise to a valuated matroid where for any linearly independent $d$-subset of columns $B \subset \{1,2,\dots ,n\}$, the value of $p(B)$ is the valuation of the corresponding $d \times d$ maximal minor.

Importantly for tropical geometry, the recipe that recovers the tropicalization of a linear subspace from the valuation of its Plücker coordinates directly generalizes to all valuated matroids, allowing us to associate a tropical linear space to every valuated matroid, not just those represented by a matrix over a field. In fact, the combinatorics of valuated matroids is perfectly compatible with that of tropical geometry, in such a way that the set of tropical linear spaces turns out to be exactly the set of tropical varieties of degree $1$, as shown by Fink in 2013. In this sense, (valuated) matroids are the mathematical object that provides the answer to what a tropical linear space should be.

A perspective on matroids that has recently gained prominence in great part due to tropical geometry is that of their associated polytopes. Given a matroid $M$ on the ground set $\{1,\dots ,n\}$, its associated matroid polytope is the polytope in $\mathbb{R}^{n}$ whose vertices are the $0/1$ indicator vectors of the bases (i.e., maximal independent sets) of $M$. For example, the matroid polytope of the uniform matroid $U_{d,n}$ in which any $d$-subset of $\{1,\dots ,n\}$ is a basis is the hypersimplex $\Delta _{d,n}$, whose vertices are the $\binom{n}{d}$ vectors with $d$ coordinates equal to $1$ and all other coordinates equal to $0$. From this polyhedral point of view, matroids can be elegantly axiomatized as follows.

Theorem 3.2 (Gelfand, Goresky, MacPherson, Serganova, 1987).

A polytope in $\mathbb{R}^{n}$ with vertices in $\{0,1\}^n$ is a matroid polytope if and only if all its edges have the form $e_i - e_j$ for $i,j \in \{1,\dots ,n\}$.

Vectors in the Dressian $\operatorname {Dr}(d,n) \subset \mathbb{R}^{\binom{n}{d}}$ can be characterized in polyhedral terms as well. They are exactly the height vectors that induce a regular subdivision of the hypersimplex $\Delta _{d,n}$ into matroid polytopes; in other words, a subdivision of $\Delta _{d,n}$ that does not introduce any new edges. Furthermore, the tropical linear space associated to a vector $p \in \operatorname {Dr}(d,n)$ turns out to be a polyhedral complex that is dual to a particular subcomplex of this regular subdivision; see Figure 4. In this way, the combinatorial properties of tropical linear spaces are tightly linked to those of matroid polytope subdivisions.

Figure 4.

A tropical line (in red) dual to a matroid subdivision of the regular octahedron $\Delta _{2,4}$. The Dressian, which is a parameter space for tropical linear spaces or valuated matroids, consists of regular subdivisions that do not introduce a new edge. It also occurs naturally in auction theory.

It is sometimes said that tropical geometry provides a tool for degenerating algebraic varieties into simpler polyhedral objects. However, already in the case of linear subspaces, we see that, while all subspaces of a vector space are quite “simple” geometrically, their tropicalizations carry somewhat intricate information about their intersections with the coordinate subspaces, in the form of valuated matroids. In fact, very natural questions about the combinatorics of tropical linear spaces—or dually, matroid polytope subdivisions—remain unanswered, such as the maximal number of faces that a tropical linear space can have. This particular question is known as the $f$-vector conjecture, stated below in terms of matroid polytope subdivisions.

Conjecture 3.3 (Speyer, 2008).

Any regular subdivision of the hypersimplex $\Delta _{d,n}$ into matroid polytopes has at most $\frac{(i-1)!}{(n-i-1)!(d+i-n)!(i-d)!}$ interior faces of dimension $i$.

The $f$-vector conjecture has been proven to hold in particular cases, such as regular subdivisions corresponding to valuated matroids that lie in the tropical Grassmannian (over $\mathbb{C}$), or in the case of maximal faces, when $i=n-1$. However, the general statement remains open.

Combinatorial Hodge theory

This tropical point of view on matroids that we have discussed has been extremely fruitful in the last few years. The local building blocks of tropical linear spaces, i.e., those subcomplexes consisting of cells containing a single fixed cell, are called Bergman fans of matroids. Combinatorially, a Bergman fan has the structure of a geometric lattice, which is a partially ordered set with special properties. Topologically, it is a cone over a bouquet of spheres. However, the particular embedding in $\mathbb{R}^{n}$ arising from tropical geometry makes Bergman fans very potent tools.

Inspired by toric geometry, Feichtner and Yuzvinsky in 2004 used this embedding to associate a certain commutative Artinian ring, called the Chow ring, to every matroid. More recently, Adiprasito, Huh, and Katz studied this ring more in depth AHK18, and showed that in fact it has a very rigid “Hodge structure,” in the sense that it resembles the cohomology ring of a smooth projective variety.

Using this powerful algebraic theory, they were able to prove long-standing conjectures about the log-concavity of certain integer sequences associated to a matroid, like the coefficients of the characteristic polynomial and the number of independent sets of a given size. Similar approaches that use other tropical spaces associated to matroids have succeeded more recently in settling other long-standing log-concavity questions in matroid theory Ard18.

Algebraic foundations of tropical geometry

Over the last few years there has been an effort to develop the algebraic foundations of tropical geometry analogous to scheme theory in algebraic geometry. Contrary to classical algebraic geometry, where information about algebraic varieties is thought of in both geometric and algebraic terms, tropical varieties have traditionally been considered as purely geometric objects. In their foundational paper GG16, Giansiracusa and Giansiracusa introduced a novel algebraic structure attached to the tropicalization of an algebraic variety, which plays the role of a “coordinate semiring” for tropical varieties. It was later understood that this algebraic information is equivalently encoded by the tropicalization of the polynomials in the ideal defining the algebraic variety, as defined in Section 1.

Given these developments, it is natural to aim to develop algebraic foundations for tropical geometry purely on the tropical side, without having to rely on the process of tropicalization of classical varieties or ideals. One possibility would be to study the class of all ideals in the semiring $\mathbb{T}[x_1,\dots ,x_n]$ of tropical polynomials, where the coefficients are taken from the set of tropical numbers $\mathbb{T}= \mathbb{R}\cup \{-\infty \}$. However, it turns out this semiring is not Noetherian, general ideals in it are not finitely generated, and their associated varieties are not necessarily polyhedral objects. This class thus extends beyond the realm of tropical geometry.

The problem with general ideals of $\mathbb{T}[x_1,\dots ,x_n]$ stems from the fact that arbitrary modules over $\mathbb{T}$ do not necessarily behave like tropical linear spaces. Maclagan and Rincón have thus proposed in MR18 the following notion as a sensible class of ideals for the study of tropical geometry.

Definition 3.4.

An ideal $I \subset \mathbb{T}[x_1,\dots ,x_n]$ is a tropical ideal if for every degree $d \geq 0$, the $\mathbb{T}$-module $I_{\leq d} \coloneq \{ f \in I : \deg (f) \leq d\}$ is a tropical linear space in the space $\mathbb{T}[x_1,\dots ,x_n]_{\leq d}$ of tropical polynomials of degree at most $d$.

The class of tropical ideals still contains the tropicalizations of all classical ideals, but it is in general much larger. This phenomenon is analogous to the fact that the class of all matroids is in general much larger than just the matroids arising from classical linear subspaces.

As shown in MR18, tropical ideals have indeed more desirable properties than general ideals of $\mathbb{T}[x_1,\dots ,x_n]$. The fact that tropical linear spaces, which make up each graded piece of a tropical ideal, have a well-behaved notion of dimension means that tropical ideals have a natural notion of Hilbert function. Just as for classical ideals, this Hilbert function eventually agrees with a polynomial, and thus, for instance, tropical ideals have a natural notion of dimension, given by the degree of this Hilbert polynomial. In addition, the varieties they define are always finite polyhedral complexes. In fact, it was proved recently in MR20 that the variety of a tropical ideal is always a polyhedral complex of dimension equal to the dimension of the tropical ideal, and furthermore, these varieties are always balanced polyhedral complexes, which generalizes part of the Structure Theorem on tropicalizations of algebraic varieties.

The algebraic foundation for tropical geometry in this direction is inherently combinatorial, as it is closely tied to tropical linear spaces and thus to matroids. Even though the theory is only in its beginnings, tropical ideals provide a strong bridge between combinatorics, algebra, and geometry, and they equip tropical varieties with richer structures beyond purely polyhedral ones.

4. Tropical Geometry, Matroids and Auctions

Auctions with indivisible goods have a strong connection to tropical geometry. Fundamental economics concepts such as utility, demand set, and competitive equilibrium can be translated into questions about tropical hypersurfaces and their corresponding regular subdivisions. With this bridge, some authors have used tropical geometry, matroid theory, and convex geometry to answer open problems in economics JKS21Tra21HLSV22. This section gives a flavor of these connections.

The simplest auction is a sealed bid auction for one good, such as an art work or a house. By the deadline, each potential buyer (agent) submits their bid. The seller announces a price $p$ and assigns the good to a bidder, who would then pay this price. The seller could offer a discount, so $p$ could be less than the highest bid, but it is expected that the highest bidder will be assigned the goods; otherwise the highest bidder will perceive the game as unfair for them.

Multi-unit combinatorial auction or product-mix auction are versions of this where there are multiple types of indivisible goods on sales. A bundle of $n$ types of goods is represented as a point in $\mathbb{Z}^n$. Each agent’s bid is no longer a single number, but a so-called valuation function $u: A \to \mathbb{R}$, where $A \subset \mathbb{Z}^n$ is the set of available bundles and $u(a)$ is how much this agent is willing to pay for bundle $a \in A$ or how much the bundle $a$ is worth to the agent. The goal for the seller is to partition the goods bundle for sale $a^\ast \in \mathbb{Z}^n$ into a sum of goods bundles $a^\ast = a^1 + \dots + a^J$, where bundle $a^j$ is assigned to agent $j$, and to find the price $p_i$ per unit of good $i$ to charge the agents, so that the game is fair for all. That is, at the announced prices $p \in \mathbb{R}^n$, there is no agent who would prefer a different bundle from what they were assigned.

Economists have long known that already for two good types and two agents, there are combinations of valuations $\{u^1, u^2\}$ where no fair pricing exists for some goods bundle $a^\ast$ (cf. Example 4.1). A central problem is thus to find reasonable rules on the auctions that restrict the set of valuations $u$ that the agents can submit, so that a fair pricing is always guaranteed, and that the allowed set of valuations is still large enough to model different types of preferences.

Recently, economists Baldwin and Klemperer BK19 made three important observations. First, the utility or profit function of an agent, which is the maximum over all available bundles of the difference between the valuation and the price, is a tropical polynomial in the (negative of) prices $p$. Second, the regular subdivision that this tropical polynomial induces on its Newton polytope tells us which goods bundles an agent would ever want to consider buying. That is, this tropical polynomial and its combinatorics store important information on demanded bundles and fair pricing. Third, when there are multiple agents, their aggregated or total utility is the tropical product of the agents’ individual tropical polynomials. The regular subdivision corresponding to the product of the tropical polynomials is called a regular mixed subdivision. It stores the combinatorial information we need to know about existence of fair pricing for all goods bundles we might want to consider in $\mathbb{Z}^n$. These observations allow us to translate economics questions into combinatorial questions about regular mixed subdivisions.

Example 4.1.

Let us construct an example of a no-fair-pricing auction based on a simplified version of Figure 2. For simplicity, suppose we have only two types of goods, tea and coffee, and two agents, Left and Right. Left wants to buy either tea or coffee, will not settle for nothing, and does not want to buy both. Right wants to buy either nothing or both coffee and tea. Left bids $3 for a 1kg pack of coffee only and $2 for a 1kg pack of tea only. Right bids $3 for both and $0 for nothing. Their utility functions are tropical polynomials in the negatives of prices:

$$\begin{align*} f_L & = (3 \odot (-p_c)) \oplus (2 \odot (-p_t)) \\ f_R & = 0 \oplus (3 \odot (-p_c) \odot (-p_t)) \end{align*}$$

where $p_c$ and $p_t$ are the prices for a 1kg package of coffee and tea, respectively. The Newton polytopes of these tropical polynomials are the two line segments in Figure 5, and the Newton polytope of the aggregate utility function $f_L \odot f_R$ is the square on the right. The point $(1,1)$ is not in the support of the aggregate utility function. This implies that if we want to sell exactly 1kg of coffee and 1kg of tea, then there is no way we can assign something to both Left and Right such that each of them gets the product bundle that maximizes their utility, at any price.

Figure 5.

Newton polytopes of utility functions for an auction of two agents with two items. See Example 4.1.

On the other hand, the point $(1,1)$ belongs to the Newton polytope of the aggregate utility function. This implies that, if the amount of coffee and tea we sell to an agent is not a discrete but a continuous quantity, and if our agents are willing to buy a convex combination of what they demanded, then there is a solution: we can set the price of coffee at $p_c = \$2$ per kg and of tea at $p_t = \$1$ per kg, and assign 500g of tea and 500g of coffee to each buyer. Then each of them gets a convex combination of the product bundles that maximize their utility: Left makes a profit of $\$1$ and Right makes a profit of $\$0$, which is the most each of them can make under such pricing. The price vector $(2,1)$ is precisely the intersection of the tropical hypersurfaces of the two tropical polynomials $f_L$ and $f_R$.

Connections to matroids

Economists are interested in conditions on the valuations $u^j$ and the pricing function $p$ (for example, beyond linear pricing) that ensure fair pricing (technically known as competitive equilibrium) is guaranteed to exist for all admissible goods bundles $a^\ast$. The ideal theorem has the format: if the valuations $u^j$ belong to some function class $\mathcal{V}$ and if the pricing functions $p$ belong to some function class $\mathcal{P}$, then competitive equilibrium always exists at any admissible goods bundle $a^\ast$. An early and influential result is due to Walras, which says that if $\mathcal{V}$ has the gross substitutes property and $\mathcal{P}$ is linear, then competitive equilibrium always exists. Figure 2, left, is an example of a function with the gross substitutes property. Interestingly, gross substitutes are certain generalizations of rank functions associated to matroids. They are called $M$-concave functions in Murota’s work on discrete convex analysis. They have several equivalent characterizations, but for our purposes, the following is the most relevant. Compare this to Theorem 3.2.

Definition 4.2.

A function $u: \mathbb{Z}^n \to \mathbb{R}$ has the gross substitutes property if each edge of the corresponding regular subdivision is parallel to one of the vectors in the set $\{e_i - e_j: 1 \leq i, j \leq n \text{ and } i \neq j\} \cup \{e_i : 1\leq i \leq n\}$.

In particular, functions with the gross substitutes property on certain subsets of the $0/1$ cubes are dehomogenized versions of points on the Dressian. This rich connection between Dressians and gross substitutes was instrumental in the solution of the matroid-based valuation conjecture in auction theory Tra21HLSV22.

Recent work concerning competitive equilibria extends the tropical framework to go beyond linear pricing, by considering embeddings of the lifted Newton polytope in higher dimensions. With this technique, BHT21 showed that for combinatorial auctions, competitive equilibrium always exists when both the pricing function and the agents’ valuations are quadratic instead of linear; that is, $p(a) = \sum _{i \in a}p_i + \sum _{i,j \in a} p_{ij}$ where $p_i$ is the price for one unit of item $i$, and $p_{ij}$ is the “discount” for buying the pair $(i,j)$ together. In a different direction, JKS21 significantly extended the results on the straight jacket auction by translating revenue optimizations in combinatorial auctions into questions about generalized permutohedra and finding roots of a system of polynomials. The connections between convex geometry and economics also go two ways: the Oda Conjecture in toric geometry can be restated in terms of product-mix auctions TY19. These results attest to the rich connections between these areas.