Introduction

In this post, we are going to discuss a bit about the intersection between algebraic geometry and matroid theory. We are all aware that June Huh, in a series of three papers, along with Eric Katz and Karim Adiprasito, developed and extended tools that led to the proof of the Heron–Rota–Welsh unimodality conjecture as well as many other open conjectures [3, 2, 1]. I once asked Huh what type of mathematition he considered himself. I, coming from structural matroid theory, initially viewed his work as a subset of algebraic geometry, but he replied that he viewed himself as a combonatorialist. I have spoken to many other mathematitions who consider themselves matroid theorists, despite not doing structural matroid theory and not having attended the sorts of conferences that I attended as a graduate student doing structural matroid theory. While we will not discuss the tools used to prove the Heron–Rota–Welsh unimodality today, this post is intended to add a bridge to the wide world of matroid theory which makes use of algebraic tools. Of course, many other mathematitions have created tools to help structural matroid theorists understand the type of matroid theory that they do.

A Combinatorial Description of (Minimal) Tropical Basis

Imagine for a moment that you and a mathematical friend are captured by an scheming matroid theorist (SMT). The SMT explains that they are going to tell you a matroid, and your friend the ground est of the matroid. The two of you will be freed when your friend can reveal the matroid to the SMT. To communicate the matroid, you are allowed to tell your friend one circuit of the matroid a day, and allowed to tell your friend when you are done telling them circuits. Your objective is to come up with a strategy that will define a matroid by a subset of the circuits. Of course, we could list every circuit, but we would like to get out of imprisonment sooner, and hence list less than every circuit.

We may be tempted, to make use of fact that binary matroids can be completely determined by listing all fundamental circuits with respect to a particular basis. But this requires, not only that we have a binary matroid, but also requires that we have a promise that our matroid is binary.

For instance, consider the graphic matroid $M(K_4)$, as labeled below. Knowing the fundamental circuits associated with the basis $\{1, 2, 3\}$, isn’t enough information to determine if $\{4, 5, 6\}$ is a circuit or not. To see this, note that both the wheel and the whirl associated with this graph have circuits $\{1,2,6\}$, $\{1,3,5\}$, and $\{2,3,4\}$.

Our strategy will involve giving our friend enough information to determine which subsets of the ground set of $M$ are flats of $M$. Note that knowing that a set $C$ is a circuit of a matroid communicates a number of sets which are not flats of a matroid. For a circuit $C$ of $M$, and a subset $X\subseteq E(M)$, we say that $C$ excludes $X$ when $|C-X|=1$. For instance, the circuit ${0,1,2}$ of $U_2,4$ excludes the subsets $\{\{0,1\}, \{0,2\}, \{1,2\}, \{0,1,3\}, \{0,2,3\}, \{1,2,3\}\}$. That is, we know that the subsets $\{\{0,1\}, \{0,2\}, \{1,2\}, \{0,1,3\}, \{0,2,3\}, \{1,2,3\}\}$ are non-flats of a matroid $M$, just by knowing that $\{0,1,2\}$ is a circuit of $M$.

Example: $U_{2,4}$

Suppose, that the SMT gives us the matroid $M=U_2,4$ on the ground set
$\{0,1,2,3\}$. Then the flats and non-flats of $M$ are:

Flats: $\emptyset$, $\{0\}$, $\{1\}$, $\{2\}$, $\{3\}$, $\{0,1,2,3\}$

Non-Flats: $\{1,2\}$, $\{1,2\}$, $\{1,3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{2,3\}$, $\{0,1,2\}$, $\{0,1,3\}$, $\{1,2,3\}$

The circuit $\{0,1,2\}$ excludes 6 of the 10 non-flats.
The circuit $\{0, 1, 3 \}$ will exclude an additional 3 non-flats, namely the flats $\{\{0, 3 \}, \{1, 3 \}, \{0, 1, 2 \} \}$. Finally, the circuit $\{0, 2, 3\}$ will exclude the set $\{2, 3,\}$.

Since the collection $\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 2, 3\} \}$ collectively excludes all the non-flats of $U_{2,4}$, we can give just these three circuits to our friend, and they will be able to determine the matroid.

Combinatorial Definition and Some Intuition

It is often useful for us to think of subsets of $[n]$ as 0-1 vectors where a vector is identified with its support. That is, a 0-1 vector $(a_0, a_2, \ldots, a_{n-1}$ represents the subset $\{x\in[n]: a_x=1\}$. For instance, $(1,0,1,0)$ represents the subset ${0,2}$ of $[4]$ because the non-zero entries of $(1,0,1,0)$ occur in the 0th and 2nd entries.

Let $M$ be a matroid on $\{0,1,\ldots, n-1\}$. We say a circuit $C$ of $M$ excludes a vector $x=(x_0, x_2, \ldots, x_{n-1})\in\{0,1\}^n$ if for exactly one $e\in C$, the entry $x_e=0$.

A collection $\mathscr{C}’\subset\mathscr{C}(M)$ is a tropical basis of $M$ if for every non-flat $S$ of $M$, there is a circuit in $\mathscr{C}’$ that excludes $S$. This was not the original definition of a tropical basis, but rather was due to Josephine Yu and Debbie S. Yuster [5].

To test if they understand the definition of a tropical basis, the reader can ask themselves why $\mathscr{C}$ is always a tropical basis of $M$.

If $e$ is a loop, then $\{e\}$ is in every tropical basis of $M$. To see this, note that
if $e$ is a loop, then $E(M)-e$ is a non-flat of $M$. The only circuit $C$ with $|C-(E-e)|=1$ is $\{e\}$.

For a tropical basis $\mathscr{C}’$ of $M$,
we say that $\mathscr{C}’$ is minimal if
for all $C\in\mathscr{C}’$,
the collection $\mathscr{C}’-C$ is not a tropical basis of $M$.

We might imagine that all minimal tropical bases of a matroid $M$ would have the same cardinality, but this in not the case. To see this, we will consider different tropical bases on $U_{2,5}$. This example is from Yu and Yuster’s paper [5].

Example: Minimal Tropical Bases for $U_{2,5}$

The nonflats of $M=U_{2,5}$ consist of all subsets of $\{0,1,2,3,4\}$ of size two, three, or four. Let $\mathscr{C}_1=\{C\in\mathscr{C}: 0\in C\}$, and let $\mathscr{C}_2=\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 1, 4\}, \{0, 2, 3 \}, \{2, 3, 4\} \}$. Note that $\mathscr{C}_1\cap \mathscr{C}_2=\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 1, 4\}, \{0, 2, 3 \} \}$. To see that $\mathscr{C}_1$ and $\mathscr{C}_2$ are tropical basis, we first note that every non-flat of $M$ besides $\{2,4\}$ and $\{3,4\}$ is excluded by a circuit in $\mathscr{C}_1\cap \mathscr{C}_2$. Both of these non-flats are excluded by $\{2,3,4\}$, so $\mathscr{C}_2$ is a tropical basis of $M$. Lastly, $\{2,4\}$ is excluded by $\{0,2,3\}$ but not by $\{0,3,4\}$, and $\{3,4\}$ is excluded by $\{0,3,4\}$ but not by $\{0,2,3\}$. So $\mathscr{C}_1$ is a tropical basis of $M$.

To see that these Tropical bases are minimal, we note that the set $\{a,b\}\in\{ \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$ is excluded by the circuit $\{0,a,b\}$, but not by any other circuit in in $\mathscr{C}_1\cup\mathscr{C}_2$.

Origional Definiton of Tropical Basis

To give the original definition, we must first understand some basic definitions in algebraic geometry. A reader who has no interest in algebraic geometry can safely skip this section.

A set is a variety if it is the solution set to some system of polynomials. For instance, the types of graphs that we drew in pre-algebra would be varieties over $\mathbb{R}^2$.

From these examples, one might guess that the union or intersection of two varieties is itself a variety. This turns out to be true.

The Tropical Semi Ring is defined by:

$$\mathbb{T}=\{\mathbb{R}\cup\infty,\oplus,\odot\}$$

$$x\oplus y=min\{x,y\}\quad\quad\quad x\odot y=x+y$$

For example, $2\oplus 7=2$ and $2\odot 7=9$.
Note that $\infty$ is the additive identity, and $0$ is the multiplicative identity.

When working with tropical numbers, generally, $(x-a)=0$ has no solution. Instead, we define a Tropical Variety as the set of points when a polynomial obtains its minimum at least twice.
For example, consider the linear polynomial

$$f(x,y)=2\odot x\oplus 1\odot y\oplus 4.$$
The variety of $f$ is equal to the set when $\min\{2+x, 1+y, 4\}$ occurs twice in the set $\{2+x, 1+y, 4\}$. When drawing tropical varieties, it can help to begin by drawing in dotted lines when any two monomials have the same value, and then fill in the parts of those dotted lines, when that value achieves the value of the polynomial. In this case, that gives us:

For a linear polynomial $f$, we call the tropical variety associated with $f$ a tropical hyperplane.

Now, for a circuit $C$ of a matroid $M$, define
$f_C(\vec{v})=\bigoplus_{e\in E} c_e\odot x_e$, where
$c_e=
\begin{cases}
0 & e\in C \\
1 & e\not\in C
\end{cases}.
$

For example, if we take $M=U_{2,5}$ and $C=\{1,2,3\}$, then
$$f_C=(0\odot x_1)\oplus (0\odot x_2)\oplus (0\odot x_3)\oplus (\infty\odot x_4)\oplus (\infty\odot x_5).$$

Consider the non-flat $\{1,2,4\}$ as an indicator vector $(1,1,0,1,0)$.
We compute $f_C(1,1,0,1,0)=(0\odot 1)\oplus (0\odot 1)\oplus (0\odot 0)\oplus (\infty\odot 1)\oplus (\infty\odot 0).$

The $min\{0+1,0+1,0+0,\infty + 1, \infty +0\}$ achieves it’s minimum only once, so $(1,1,0,1,0)$ is not in the tropical hyperplane associated with $\{1,2,4\}$.

We denote the tropical hyperplane associated with $f_C$ as $T(C)$. That is, $T(C)$ is the space of all vectors $v$ where $f_C(v)$ achieves it’s minimum twice.

For $\mathscr{C}’\subseteq\mathscr{C}(M)$, we define $T(\mathscr{C}’)$ as $\bigcap_{C\in\mathscr{C}}’T(C)$.
A set $\mathscr{C}’\subseteq\mathscr{C}$ is a tropical basis for $M$ if $T(\mathscr{C}’)=T(\mathscr{C})$.

Lemma[5]
For any $\mathscr{C}’\subseteq \mathscr{C}$,

$$T(\mathscr{C}’)\cap\{0,1\}^n=T(\mathscr{C})\cap\{0,1\}^n$$ if and only if $$T(\mathscr{C}’)=T(\mathscr{C}).$$

Before we give the proof of this lemma, it is important to note that this lemma is the essential reason why we are able to use the combinatorial definition of a tropical basis. Intersecting spaces with indicator vectors allows us to only consider the vectors which can be viewed as as subsets of the ground set of a matroid.

Proof
Of course $T(\mathscr{C})\subseteq T(\mathscr{C}’)$. So suppose that $x \in T(\mathscr{C}’)-T(\mathscr{C})$. We need to find an $\tilde{x}\in (T(\mathscr{C}’)\cap\{0,1\}^n)-(T(\mathscr{C})\cap\{0,1\}^n)$.

Since $x\not\in T(\mathscr{C})$, there is some circuit $C_x\in \mathscr{C}$, that excludes $x$, that is $\{x_i:i\in C_x\}$ has a unique minimum $m$.

\[\tilde{x}= \begin{cases}
1 & \text{if } x_i>m\\
0 & \text{if } x_i \leq m.
\end{cases}
\]

$\tilde{x}$ is excluded by $C_x$ because $\{\tilde{x}_i:i\in C_x\}$ achieves it’s minimum exactly when $\{x_i:i\in C_x\}$ has its unique minimum. So $\tilde{x}$ is not in $T(\mathscr{C})$. For any circuit $D$ where $\{x_i:i\in D\}$ achieves its minimum twice, so does $\{\tilde{x}_i:i\in D\}$. So no circuit of $\mathscr{C}’$ excludes $\tilde{x}$. ♦

Open Questions

People have been interested in finding canonical minimal tropical bases for common classes of matroids. In particular, Yu and Yuster [5] asked as an open question to find a minimal tropical basis for an arbitrary transversal matroid. They gave a rather nice description o a canonical minimal tropical basis for uniform matroids.

Yu and Yuster [5] also showed that graphic matroids, cographic matroids, and $R_{10}$ have unique minimal tropical basis. They hypothesised that all regular matroids would have a unique minimal tropical basis. In fact, Yasuhito Nakajima [4] showed that all binary matroids have a unique minimal tropical basis.

Nakajima [4] also showed that having a unique minimal tropical basis was not closed under taking minors. The example that they gave also shows that some non-binary matroids have a unique minimal tropical basis.

It would be nice to have a characterization of which matroids had a unique minimal tropical basis.

 

References