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