Sparse representations of binary matroids

Let us call the sparsity of a binary matroid $M$ the minimum number of $1$’s in a binary matrix representation of $M$. There are many practical reasons to desire such a representation – matrices with few non-zero entries can be encoded and manipulated much more efficiently. So it would be really nice to have an algorithm which can efficiently perform row reductions in order to sparsify a binary matrix, even to within a very rough approximation of the optimal value.

Given the importance of this problem, I’m surprised that I haven’t seen more work on it from the matroid theory community. So this blog post aims to publicize the area, share some questions I have been wondering about, and ask the community for pointers to more work in this direction.

We consider classes of binary matroids which are closed under minors. For which such classes is the sparsity at most linear in the rank? Parallel edges cause silly problems, so we only consider the simple matroids in the class. If the number of elements is not linear in the rank, then neither is the sparsity. So a necessary condition is that the class forbids the cycle matroid of some clique. Is this obvious necessary condition also sufficient? Surely not, right?!

Problem 1: Is it true that for each integer $t$, there exists an integer $c=c(t)$ so that if $M$ is a simple rank-$r$ binary matroid without a minor isomorphic to the cycle matroid of a $t$-vertex clique, then $M$ has a representation with at most $c r$ many $1$’s?

Such a matroid $M$ has at most linearly many elements by the Growth Rate Theorem. Problem 1 asks if we can additionally bound the average number of $1$’s per column. This is possible for graphic classes since we can just take the incidence matrix. However, I would guess that the answer is no in general, even for matroids of bounded branch-width.

What if we only consider representations which are in reduced row echelon form? This added restriction probably makes it much harder to sparsify. For a graph $G$ from a minor-closed class, this means that we want to bound the minimum, over all spanning trees $T$, of the average length of a fundamental cycle. (For each edge $e \in E(G) \setminus E(T)$ , its fundamental cycle is the unique cycle of $T+e$.) The best candidate I have found for a graph that is not sparsifiable in this sense is a big grid.

Problem 2: Is it true that for each integer $k$, there exists an integer $n=n(k)$ so that if $T$ is any spanning tree of the $n \times n$ grid, then the average length of a fundamental cycle with respect to $T$ is at least $k$?

Pablo Blanco’s undergraduate thesis [1] at Princeton considered another notion of sparsity which is typically harder to obtain. From the matrix perspective, we want to find a matrix which is in reduced row echelon form and, additionally, avoids an all $1$’s submatrix of fixed size. He proposed a conjecture about graphs which suggests that the main obstructions are the following (planar) graph and its dual. The $k$-banana is the graph which is obtained from $k$ paths of length $k$ by identifying all of their starting vertices into one vertex $s$, and all of their ending vertices into one vertex $t$.

Let me also point out that Kristýna Pekárková has a really nice master’s thesis [2] which takes care of the bounded branch-depth case of sparsification quite nicely.

[1] Pablo Blanco, Graphs with Large Overlap in Their Spanning Trees, click here for info

[2] Kristýna Pekárková, Matroid Based Approach to Matrix Sparsification, click here for pdf

Delta-Modular Matroids

The goal of this post is to entice readers to work with an interesting class of matroids that has important connections with the theory of integer programming. These matroids are called Delta-modular, and they are a natural generalization of regular matroids. After giving some background information, I will state and discuss some fundamental properties of Delta-modular matroids, and then state and discuss some important open problems concerning these matroids. 

Introduction

A fundamental problem in integer programming is to solve the following Integer Linear Program (ILP): find $\textrm{max}\{c^Tx \mid Ax \le b \textrm{ and } x \in \mathbb Z^n\}$ where $A \in \mathbb Z^{m \times n}$, $b \in \mathbb Z^m$, and $c \in \mathbb Z^n$. This problem is $\mathcal N\mathcal P$-hard, but we can hope for better efficiency if the matrix $A$ has special structure. Given a positive integer $\Delta$, an integer matrix $A$ is $\Delta$-modular if the absolute value of every $\textrm{rank}(A) \times \textrm{rank}(A)$ submatrix of $A$ is at most $\Delta$. A classic result of Hoffman and Kruskal [HK56] implies that ILPs over 1-modular (or unimodular) matrices can be solved in strongly polynomial time. After about 60 years with little progress, a breakthrough result of Artmann, Weismantel, and Zenklusen showed that ILPs over 2-modular (or bimodular) matrices can be solved in strongly polynomial time [AWZ17]. Determining the complexity for solving ILPs over $\Delta$-modular matrices with $\Delta \ge 3$ is a major open problem in the theory integer programming.

The proof of Artmann, Weismantel, and Zenklusen heavily relies on structural properties of 2-modular matrices. This is where matroids come in! For each positive integer $\Delta$ we say that a matroid is $\Delta$-modular if it has a representation over $\mathbb Q$ as a $\Delta$-modular matrix, and we write $\mathcal M_{\Delta}$ for the class of $\Delta$-modular matroids. The hope is that studying $\mathcal M_{\Delta}$ via techniques from structural matroid theory will uncover new properties of $\Delta$-modular matrices that are relevant for integer programming. However, $\mathcal M_{\Delta}$ is also a very natural class of matroids, because $\mathcal M_1$ is precisely the class of regular matroids!

Properties

Even though $\mathcal M_{1}$ is fundamental in integer programming and matroid theory, little is known about $\Delta$-modular matroids when $\Delta \ge 2$. Below is a list of five properties that will likely be important for future work with these matroids.

Property 1: For all $\Delta \ge 1$, the class $\mathcal M_{\Delta}$ is closed under minors and duality.

Closure under minors was proved in [Proposition 8.6.1, GNW22] and closure under duality was proved by D’Adderio and Moci [Theorem 2.2, DM13] using arithmetic matroids, although a more direct proof due to Marcel Celaya can be found in [Theorem 4.2, OW22]. Of course, Property 1 is crucial for using techniques from structural matroid theory to study $\mathcal M_{\Delta}$.

Property 2: For all $\Delta \ge 1$, every matroid in $\mathcal M_{\Delta}$ is representable over every field with characteristic greater than $\Delta$.

This follows from the fact that if $A$ is a $\Delta$-modular matrix and $p$ is a prime greater than $\Delta$, then the set of all $\textrm{rank}(A)\times \textrm{rank}(A)$ submatrices of $A$ with non-zero determinant does not change if we perform all calculations modulo $p$. In particular, every matroid in $\mathcal M_2$ is dyadic, and every matroid in $\mathcal M_3$ is $\textrm{GF}(5)$-representable. Also, since there is a prime in the interval $(\Delta, 2\Delta]$ by Chebyshev’s Theorem, Property 2 implies that the uniform matroid $U_{2, 2\Delta + 2}$ is not in $\mathcal M_{\Delta}$. Again, Property 2 is crucial because it allows for the potential use of tools from the study of matroids representable over partial fields.

Property 3: When $\Delta \ge 2$, the class $\mathcal M_{\Delta}$ is not closed under direct sums.

This is where $\mathcal M_{\Delta}$ differs from matroid classes defined by representability over a partial field, which are always closed under direct sums. Intuitively, Property 3 is true because a block-diagonal matrix for which each block is $\Delta$-modular may not be $\Delta$-modular itself. As a particular example of Property 3, the uniform matroid $U_{2,4}$ is in $\mathcal M_2$, but $U_{2,4} \oplus U_{2,4}$ is not in $\mathcal M_2$ [Proposition 4.4, OW22].  

Property 4: If $r$ is sufficiently large as a function of $\Delta$, then every simple rank-$r$ matroid in $\mathcal M_{\Delta}$ has at most $\binom{r+1}{2} + 80\Delta^7 \cdot r$ elements [Theorem 1.3, PSWX24].

The problem of finding upper bounds on the number of columns of a rank-$r$ $\Delta$-modular matrix has received a lot of recent attention, because this also provides bounds for important parameters associated with ILPs over $\Delta$-modular matrices; see [LPSX23] for details. The bound in Property 4 was proved with techniques from matroid theory, and is currently the best known bound for fixed $\Delta$.

Property 5: $\mathcal M_{\Delta}$ contains no spikes with rank greater than $2\Delta$ [Proposition 2.1, PSWX24].

This was a key fact used in the proof of Property 4, and also differs from the typical situation for matroids over partial fields. Since spikes are notoriously `wild’, this is good news!

Open Problems

Since the study of $\Delta$-modular matroids is so new, there are many open problems.

Problem 1: Let $\mathcal M_{\Delta}^t$ be the class of matroids with a representation as a totally $\Delta$-modular matrix. Is $\mathcal M_{\Delta}^t = \mathcal M_{\Delta}$?

An integer matrix $A$ is totally $\Delta$-modular if the determinant of every square submatrix has absolute value at most $\Delta$. When $\Delta \le 2$, every $\Delta$-modular matrix is projectively equivalent to a totally $\Delta$-modular matrix, so Problem 1 has an affirmative answer when $\Delta \le 2$. However, when $\Delta \ge 3$ it is unclear whether every $\Delta$-modular matrix is projectively equivalent to a totally $\Delta$-modular matrix, so new ideas may be needed.

Problem 2: Find an absolute constant $C$ so that if $r$ is sufficiently large, then every simple rank-$r$ matroid in $\mathcal M_{\Delta}$ has at most $\binom{r+1}{2} + C\Delta\cdot r$ elements.

This is a natural next step from the bound in Property 4. There is a lower bound of $\binom{r+1}{2} + (\Delta – 1)(r – 1)$ that holds for all $\Delta \ge 1$ (see [Proposition 1, LPSX23]), so the bound in Problem 2 would be tight up to the constant $C$. While this lower bound is the correct answer for $\Delta = 1$ [Hel57] and $\Delta = 2$ [OW22, LPSX23], a recent construction of Averkov and Schymura [Theorem 1.3, AS22] does better for $\Delta \in \{4, 8, 16\}$, so there is no obvious choice for $C$ that is tight for all $\Delta$. 

Problem 3: Find a class $\mathcal N$ of matroids so that ILPs with $\Delta$-modular constraint matrix $A$ with $M(A) \in \mathcal N$ can be solved in polynomial time.

This is in the spirit of a recent result showing that ILPs over $\Delta$-modular matrices for which each row has at most two nonzero entries can be solved in strongly polynomial time [FJWY22]. Perhaps the most interesting choice for $\mathcal N$ would be the class of projections of graphic matroids, because the matroids in $\mathcal M_{\Delta}$ providing the best known lower bound in Problem 2 are projections of graphic matroids.

Problem 4: Find the list of excluded minors for $\mathcal M_{2}$.

Since $\mathcal{ M}_{\Delta}$ is minor-closed and every matroid in $\mathcal M_{\Delta}$ is representable over finite fields by Property 2, Rota’s Conjecture says that $\mathcal M_{\Delta}$ has a finite list of excluded minors. Tutte showed that $\mathcal M_{1}$ has only three excluded minors: $U_{2,4}$, the Fano plane $F_7$, and its dual $F_7^*$ [Tut58]. It should be feasible (but difficult) to use existing techniques to find the list of excluded minors when $\Delta = 2$; there is a more detailed discussion in [OW22]. 

Problem 5: Find a decomposition theorem for $\mathcal M_{2}$.

Seymour’s celebrated decomposition theorem says that every internally $4$-connected matroid in $\mathcal M_1$ is graphic, cographic, or a specific $10$-element matroid $R_{10}$ [Sey80]. Do matroids in $\mathcal M_2$ satisfy a similar property? If a decomposition can be found efficiently for $\mathcal M_2$, it would have several interesting consequences. For example, it would likely give a new proof that ILPs over 2-modular matrices can be solved in polynomial time. It would also likely give a polynomial-time algorithm for determining if a given matrix is 2-modular; this recognition problem is open for $\Delta$-modular matrices when $\Delta \ge 2$. While Problem 5 is certain to be difficult, it would likely be worthwhile to use the approach of [MNvZ11] and [CMN15] to systematically study what such a decomposition would look like. Of course, this problem is also highly interesting for $\mathcal M_{\Delta}$ with $\Delta \ge 3$.

References

[AWZ17] S. Artmann, R. Weismantel, R. Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1206-1919, 2017.

[AS22] G. Averkov, M. Schymura. On the maximal number of columns of a Delta-modular matrix. In K. Aardal and Laura L. Sanità, editors, Integer Programming and Combinatorial Optimization, pages 29-42, Cham, 2022. Springer International Publishing.

[CMN15] C. Chun, D. Mayhew, M. Newman. Obstacles to decomposition theorems for sixth-root-of-unity matroids. Ann. Combin., 19:79-93, 2015.

[DM13] M. D’Adderio, L. Moci. Arithmetic matroids, the Tutte polynomial, and toric arrangements. Adv. in Math., 232:335-367, 2013.

[FJWY22] S. Fiorini, G. Joret, S. Weltge, Y. Yuditsky. Integer programs with bounded subdeterminants and two nonzeros per row. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 13-24, 2022.

[GNW22] J. Geelen, P. Nelson, Z. Walsh. Excluding a line from complex-representable matroids. To appear in Mem. Amer. Math. Soc.

[Hel57] I. Heller. On linear systems with integral valued solutions. Pac. J. Math., 7(3):1351-1364, 1957.

[HK56] A. Hoffman, J. Kruskal. Integral boundary points of convex polyhedra. Linear Inequalities and Related Systems, 24:223-246, 1956.

[LPSX23] J. Lee, J. Paat, I. Stallknecht, L. Xu. Polynomial upper bounds on the number of differing columns of Delta-modular integer programs. Math. Oper. Res., 48(4):1811-2382, 2023.

[MWvZ11] D. Mayhew, G. Whittle, S. H. M. van Zwam. An obstacle to a decomposition theorem for near-regular matroids. SIAM J. Disc. Math., 25(1):271-279, 2011.

[OW22] J. Oxley, Z. Walsh. 2-Modular matrices. SIAM J. Disc. Math., 36:1231-1248, 2022.

[PSWX24] J. Paat, I. Stallknecht, Z. Walsh, L. Xu. On the column number and forbidden submatrices for Delta-modular matrices. SIAM J. Disc. Math., 38:1-18, 2024.

[Sey80] P. D. Seymour. Decomposition of regular matroids. J. Combin. Theory Ser. B, 28:305-359, 1980.

[Tut58] W. T. Tutte. A homotopy theorem for matroids, I, II. Trans. Amer. Math. Soc., 88, 144-174, 1958.

 

 

Online Talk: James Oxley

YouTube recording: https://www.youtube.com/watch?v=fKgb4XxhQzk

Time: Wednesday, April 24 at 3pm ET
Zoom: https://gatech.zoom.us/j/8802082683

Speaker: James Oxley, Louisiana State University
Title: The legacy of Dominic Welsh

Abstract: Dominic Welsh wrote the first comprehensive text on matroids. He supervised 28 doctoral theses and wrote over 100 papers and five books. As impressive as these numbers are, they fail to truly capture the spirit of the man who inspired generations of students and imbued them with not only a love of mathematical beauty but with a deep and abiding affection for the man himself. Dominic died in November, 2023. The speaker will attempt to capture some of the key aspects of his legacy.

Intro to Tropical Bases

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


[1] Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries, Annals of Mathematics 188 (2018), 381–452.

[2] June Huh, Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs,Journal of the American Mathematical Society 25 (2012), 907–927.

[3] June Huh and Eric Katz, Log-concavity of characteristic polynomials and the Bergman fan of matroids, Mathematische Annalen 354 (2012), 1103–1116.

[4] Yasuhito Nakajima, Minimal tropical basis for Bergman fan of matroid, arXiv
preprint arXiv:1901.06893 (2019), https://arxiv.org/abs/1901.06893, doi:
10.48550/arXiv.1901.06893, Submitted on 21 Jan 2019 (v1), last revised 21 Feb 2019 (this
version, v2).

[5] Josephine Yu (UC Berkeley) and Debbie S. Yuster (Columbia University), Representing trop-
ical linear spaces by circuits, arXiv:math/0611579 [math.CO], https://arxiv.org/abs/math/
0611579, doi: 10.48550/arXiv.math/0611579.