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.
- Find $\pi_{\mathsf M}(r, U_{2,t+2})$ when t is not a prime power.
- Find $\pi_{\mathsf M}(r, U_{q,q+2})$ when q is a prime power.
- Find $\pi_{\mathsf M}(r, U_{s,s+1})$ for $s \ge 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.