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.