What is the maximum number of bases of an n-element, rank-r matroid? This question is not interesting: the answer the answer is $\binom{n}{r}$, and equality holds only for the uniform matroid $U_{r,n}.$ However, if we exclude a fixed uniform matroid as a minor, this problem becomes much more interesting.

Problem 1: What is the maximum number of bases of an n-element, rank-r matroid with no $U_{s,t}$-minor? Call this number $\text{ex}_{\mathsf M}(n, r, U_{s,t})$.

To avoid issues with the parity of n and small sporadic examples, I will focus on the following relaxation of Problem 1, which asks for the asymptotically maximum basis density for rank-r matroids with no $U_{s,t}$-minor.

Problem 2: What is $\lim_{n \to\infty}\frac{\text{ex}_{\mathsf M}(n, r, U_{s,t})}{\binom{n}{r}}$? Call this number $\pi_{\mathsf M}(r, U_{s,t})$.

In this post I will discuss recent joint work with Jorn van der Pol and Michael Wigal [vdPWW25+] on these problems, with an emphasis on the following two points. First, Problems 1 and 2 are the specializations of the Turán number and Turán density of the daisy hypergraph $\mathcal D_r(s, t)$ to the class of matroid basis hypergraphs. Second, Problems 1 and 2 lead to many interesting related open problems of varying levels of difficulty. I hope that the interested reader will solve some of these open problems!

The Turán Density of a Daisy

I’ll begin with the original motivation for Problem 1: it is the Turán number of the daisy hypergraph $\mathcal D_r(s,t)$ within the class of matroid basis hypergraphs. I will briefly explain what this means, and why it is interesting. For all integers r,s,t with $r,t \ge s \ge 1$, an (r, s, t)-daisy, denoted $\mathcal D_r(s,t)$, is an r-uniform hypergraph with vertex set $S \cup T$ and edge set $\{S \cup X \mid X \in T^{(s)}\}$, where S is an (r – s)-element set, T is a t-element set disjoint from S, and $T^{(s)}$ is the set of all s-element subsets of T. The set S is the stem and the sets in $T^{(s)}$ are the petals. Note that $\mathcal D_r(s,t)$ has $\binom{t}{s}$ edges, that $\mathcal D_s(s, t)$ is simply the t-vertex, s-uniform hypergraph $K^{(s)}_t$, and that $\mathcal D_r(s,t)$ is a subgraph of both $\mathcal D_r(s , t+1)$ and $\mathcal D_r(s+1, t+1)$. See Figure 1 for some examples of daisies.

Daisies were first defined explicitly by Bollabás, Leader, and Malvenuto, who showed that a well-known problem about the hypercube graph [Conjecture 8, BLM11] is equivalent to a natural conjecture about the Turán densities of daisies. The Turán number of an r-uniform hypergraph H, denoted $\text{ex}(n, r, H)$, is the maximum number of edges of an n-vertex, r-uniform hypergraph without H as a subgraph, and the Turán density of H is $\pi(r, H) = \lim_{n \to\infty}\frac{\textrm{ex}(n, r, H)}{\binom{n}{r}}$. These parameters are very well-studied; see Keevash’s survey [K11]. Bollobás, Leader, and Malvenuto conjectured that $\lim_{r \to \infty} \pi(\mathcal D_r(s,t)) = 0$ for all integers s and t with $t \ge s \ge 1$ [Conjecture 4, BLM11], which is a natural conjecture because as r grows, the daisy $\mathcal D_r(s,t)$ becomes sparser and sparser and therefore should be harder to avoid as a subgraph. However, this conjecture was recently disproved by Ellis, Ivan, and Leader for all $t \ge s \ge 2$ [Theorem 5, EIL24].

Theorem 1 [EIL24]: If q is a prime power, then $$\lim_{r \to \infty} \pi(\mathcal D_r(2, q + 2)) \ge \prod_{i=1}^{\infty} (1 – q^{-i}).$$

This is where matroids come into play: the hypergraphs used to find this lower bound are basis hypergraphs of $\mathbb F_q$-representable matroids, meaning that the vertex set is the ground set of the matroid and the edge set is the basis set of the matroid. In [vdPWW25+] we explored the construction used to prove Theorem 1 and found a connection between daisies and matroids: the basis hypergraph of a rank-r matroid M has a $\mathcal D_r(s,t)$-subgraph if and only if M has a $U_{s,t}$-minor [Corollary 2.3, vdPWW25+]. So $\textrm{ex}_{\mathsf M}(n, r, U_{s,t})$ is the maximum number of edges of an n-element, rank-r matroid basis hypergraph without $\mathcal D_r(s,t)$ as a subgraph. Therefore, $\textrm{ex}_{\mathsf M}(n, r, U_{s,t}) \le \textrm{ex}(n, r, \mathcal D_r(s,t))$ and $\pi_{\mathsf M}(r, U_{s,t}) \le \pi(r, \mathcal D_r(s,t))$, so Problems 1 and 2 give an approach for finding new lower bounds for $\lim_{r \to \infty} \pi(\mathcal D_r(s,t))$, which in turn would likely lead to new insights into the hypercube graph.

Results

The basis density parameter $\pi_{\mathsf M}(r, U_{s,t})$ is known in only a few nontrivial cases. In light of Theorem 1, the case $(s, t) = (2, q + 2)$ for a prime power q is particularly interesting.

Theorem 2 [vdPWW25+]: If $r \ge 2$ and $q$ is a prime power, then $$\pi_{\mathsf M}(r, U_{2,q + 2}) = r! \cdot \left(\frac{q – 1}{q^r – 1}\right)^r \cdot b(r,q),$$ where $b(r,q)$ is the number of bases of the rank-r projective geometry over the finite field of order q. In particular, $\lim_{r \to \infty} \pi_{\mathsf M}(r, U_{2,q+2}) = \prod_{i=1}^{\infty} (1 – q^{-i})$.

This was proved for q = 2 by Alon [A24] but was unknown in all other cases. Interestingly, Theorem 2 shows that one cannot use matroid basis hypergraphs to improve the lower bound of Theorem 1. The key to the proof is a theorem of Kung [K93] that upper bounds the number of points of a rank-r matroid with no $U_{2,q + 2}$-minor.

The only other known instances of Problem 2 are for the smallest nontrivial values of s and t.

Theorem 3 [vdPWW25+]: If $r \ge 3$, then $\pi_{\mathsf M}(r, U_{3,4}) = \frac{r! \cdot 2^{\lfloor r/2 \rfloor}}{r^r}$.

The proof is straightforward and relies on the fact that every matroid with no $U_{3,4}$-minor is a direct sum of matroids with rank at most two. The instance $(s,t) = (3,5)$ is more difficult, and we were only able to solve the case $r = 3$.

Theorem 4 [vdPWW25+]: $\pi_{\mathsf M}(3, U_{3,5}) = 3/4$.

However, this is notable because Turán [T41] conjectured that $\pi(3, K_5^{(3)}) = 3/4$, so Theorem 3 shows that this conjecture holds within the class of matroid basis hypergraphs, via the connection described in the previous section. The proof of Theorem 4 is structural, and relies on the fact that every rank-3 matroid with no $U_{3,5}$-restriction either has no $U_{2,5}$-minor or can be covered by two lines [Lemma 6.4, vdPWW25+].

Open Problems

In light of Theorems 2, 3, and 4, there are several instances of Problem 2 that may not be difficult to solve.

1. Find $\pi_{\mathsf M}(r, U_{2,t+2})$ when t is not a prime power.
2. Find $\pi_{\mathsf M}(r, U_{q,q+2})$ when q is a prime power.
3. Find $\pi_{\mathsf M}(r, U_{s,s+1})$ for $s \ge 4$.
4. Find $\pi_{\mathsf M}(3, U_{3,t})$ for $t \ge 6$.

A solution to (1) would surely use a theorem of Geelen and Nelson about the number of points of a rank-r matroid with no $U_{2,t+2}$-minor [GN15], so when r is sufficiently large I expect that $\pi_{\mathsf M}(r, U_{2,t+2}) = \pi_{\mathsf M}(r, U_{2,q+2})$ where q is the largest prime power at most t. For (2), I expect that $\pi_{\mathsf M}(r, U_{q,q+2}) = \pi_{\mathsf M}(r, U_{2,q+2})$. Problem (3) is interesting because $\pi_{\mathsf M}(r, U_{s,s+1})$ is the asymptotic maximum basis density for rank-r matroids with circumference at most s. It seems likely that the densest such matroids are direct sums of uniform matroids with rank at most s – 1. Finally, for (4) it seems like the answer should be given by the freest rank-3 matroids that can be covered by $(t-1)/2$ lines when t is odd, or by $(t – 2)/2$ lines and one point when t is even.

I’ll close by discussing some interesting problems related to Problems 1 and 2, beginning with the following generalization of Problem 1.

Problem 3: Let $\mathcal M$ and $\mathcal F$ be sets of matroids. What is the maximum number of bases of an n-element, rank-r matroid in $\mathcal M$ with no minor in $\mathcal F$? 

This problem has many interesting special cases. For example, when $\mathcal M$ is the class of graphic matroids and $\mathcal F$ is empty, Problem 3 is asking for the maximum number of spanning trees among all n-edge, (r+1)-vertex graphs, which has been solved for many choices of n and r by Kelmans [K96]. It would be interesting to obtain the binary analogue of Kelmans’ results.

Problem 4: Find the maximum number of bases of an n-element, rank-r binary matroid.

This is just Problem 1 for $(s,t) = (2,4)$, and is most interesting when $n < 2^r – 1$. When $n = 2^r – 2^{r – c}$ for some $c \ge 1$ it seems likely that the number of bases will be maximized by the rank-r Bose-Burton geometry on n elements, but it is unclear what the answer should be for other values of n.

In the case that $\mathcal M$ is the class of rank-3 affine matroids over $\mathbb R$ and $\mathcal F$ is empty, Problem 3 has a more geometric flavor.

Problem 5: Among all sets of n points in $\mathbb R^2$ with no t in general position, what is the maximum number of non-collinear triples?

Theorems 3 and 4 can be used to solve this problem when t = 4 or 5, but this problem is open for all t at least six. Of course, one can also replace $\mathbb R^2$ with $\mathbb F^s$ for any field $\mathbb F$ and integer $s \ge 2$, and seek to maximize the the number of s-sets in general position. However, Problem 5 as stated is in some sense dual to a still-open problem of Erdős [E88]: among all sets of n points in $\mathbb R^2$ with no four on a line, what is the maximum cardinality of a subset in general position, in the worst case? 

Clearly Problem 3 has a wide variety of specializations, so I hope that every matroid theorist can find (and solve!) some instance that suits their interests.

References

[A24] N. Alon. Erasure list-decodable codes and Turán hypercube problems. Finite Fields and Their Applications, 100:102513, 2024.

[BLM11] B. Bollabás, I. Leader, C. Malvenuto. Daisies and other Turán problems. Combin. Probab. Comput,, 20(5):743—747, 2011.

[EIL24] D. Ellis, M.-R. Ivan, I. Leader. Turán densities for daisies and hypercubes. Bull. London Math. Soc., 56(12):3838—3853, 2024.

[E88] P. Erdős. Some old and new problems in combinatorial geometry. In Applications of discrete mathematics (Clemson, SC, 1986), pages 32—37, 1988.

[GN15] J. Geelen, P. Nelson. The number of points in a matroid with no n-point line as a minor. J. Combin. Theory Ser. B, 100(6):625—630, 2010.

[K11] P. Keevash. Hypergraph Turán problems. In Surveys in combinatorics, volume 392 of London Math. Soc. Lecture Note Ser., pages 83—139. Cambridge Univ. Press, Cambridge, 2011.

[K96] A. Kelmans. On graphs with the maximum number of spanning trees. Random Struct. Algorithms, 9:177—192, 1996.

[K93] J. P. S. Kung. Extremal matroid theory. In Graph structure theory (Seattle, WA, 1991), volume 147 of Comtemp. Math., pages 21—61. Amer. Math. Soc., Providence, RI, 1993.

[T41] P. Turán. On an extremal problem in graph theory. Mat. Fiz. Lapok, 48:436—452, 1941.

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.