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

There is a wonderful matroidal proof of the Tutte-Berge formula for the maximum size of a matching [1]. Today we discuss another min-max theorem [2] which has a similar matroidal proof. Tantalizingly, the two theorems do not (yet?!) have a common generalization. This theorem was just posted to arXiv by yours truly – it arose from joint work with Jim Geelen and Paul Wollan on vertex-minors, which I’ll have to discuss later!

Matchings and the proof strategy

First we outline the proof in the case of matchings. It’s more convenient to work in the “dual setting”. So, given a graph $G$, we write $\textrm{defect}(G)$ for the minimum number of vertices left uncovered by a matching. So, where $\nu(G)$ denotes the size of a maximum matching of $G$, we have $\textrm{defect}(G) = |V(G)|-2\nu(G)$.

We write $\textrm{odd}(G)$ for the number of components of a graph $G$ with an odd number of vertices. Note that for any $X \subseteq V(G)$, we have $\textrm{defect}(G)  \ge \textrm{odd}(G-X)-|X|$, since all but $|X|$ of the odd components must contribute towards the defect. The min-max theorem says that in fact equality can be achieved.

Theorem (Tutte-Berge Formula): For any graph $G$,
$$\textrm{defect}(G) = \max_{X \subseteq V(G)} \left(\textrm{odd}(G-X)-|X|\right).$$

Here is a rough roadmap on using matroids to prove min-max theorems like this one. This strategy is due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour [1], who use it to prove a theorem which does generalize the Tutte-Berge Formula.

1. Find a matroid whose rank equals the defect. In this case, sets which are of the form $V(G)\setminus V(M)$ for some maximum matching $M$ form the bases of a matroid. This is the dual of the well-known matching matroid.
2. Reduce to the case that the matroid is loopless. In this case, no vertex-minimum counterexample can contain a loop vertex $v$. Otherwise, we would have $\textrm{defect}(G)<\textrm{defect}(G-v)$, and so we could add $v$ to the set $X$ obtained for $G-v$ to get a “good set” for $G$ and thus a contradiction.
3. Use transitivity of parallel pairs to complete the proof. In this case, each component of $G$ has rank $1$ by transitivity of parallel pairs and the fact that for each edge $uv \in E(G)$, the vertices $u$ and $v$ are parallel (that is, there is no maximum matching which leaves both $u$ and $v$ uncovered). So we can take $X = \emptyset$ since each component is odd and contributes $1$ towards the defect.

The new min-max theorem

The new min-max theorem is for “rooted Eulerian signed graphs”, which is a bit of a mouthful. The point is that we have a (multi-)graph $G$ which is Eulerian (connected and with every vertex of even degree), a specified vertex $b \in V(G)$ called the root, and a specified set of edges $S \subseteq E(G)$ called the signature. It is helpful to think of the edges in $S$ as being “odd” and the other edges as being “even”.

Since $G$ is Eulerian, it is possible to partition its edge-set into exactly $\textrm{degree}(b)/2$ many parts, each of which is the edge-set of a trail that begins and ends at $b$. We call such a trail a $b$-trail, and we say that it is odd if it contains an odd number of edges from $S$. We are interested in the following maximization problem.

Problem: What is the maximum number of odd trails in a collection of $\textrm{degree}(b)/2$ many $b$-trails which partitions $E(G)$?

We call this the flooding number and denote it by $\widetilde{\nu}$. The min-max theorem for $\widetilde{\nu}$ is somewhat technical to state, so we refer the reader to [2]. However, here is an example of our version of an “odd component”. The thick red edges denote the edges in $S$. Look at the parity of $|S|$ and notice that $\widetilde{\nu}$ is $3$ rather than $\textrm{degree}(b)/2$, which is $4$.

The general outline of the proof is exactly the same as before. We define a matroid of rank $\textrm{degree}(b)/2-\widetilde{\nu}$; this quantity is our analog of the “defect”. We then reduce to the case that this matroid is loopless and use transitivity of parallel pairs to get “odd components”. These two proofs are too similar for coincidence! So, the question is:

Question: Is there a construction which reduces the matching number $\nu$ to the flooding number $\widetilde{\nu}$, or vice-versa?

[1] Section 3 of “Packing Non-Zero A-Paths In Group-Labelled Graphs” by Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour, Combinatorica, 2006.
[2] “Decomposing a signed graph into rooted circuits” by McCarty, arXiv:2308.01456, 2023.