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.

My PhD student, Nate Vaduthala, and I have been working on a paper about flag matroids that will (hopefully) hit the arXiv in the next week or two. In this blog post, I will give an introduction to flag matroids with particular attention to representability questions, and then state one of our results about flag matroids that are representable over the field of order 2.

Given a field $\mathbb{K}$ and a finite set $E$, we let $\mathbb{K}^E$ denote the $\mathbb{K}$-vector space with a distinguished set of coordinates indexed by $E$. Each $S \subseteq E$ gives a coordinate projection $\pi_S: \mathbb{K}^E \rightarrow \mathbb{K}^S$ that sends each $(x_e)_{e \in E}$ to $(x_e)_{e \in S}$. Each linear subspace $L \subseteq \mathbb{K}^E$ defines a representable matroid $\mathcal{M}_L$ where $S \subseteq E$ is independent whenever $\pi_S(L)$ has dimension $|S|$. Thus one can view matroids as a combinatorial abstraction of linear subspaces.

Now suppose we have two nested linear subspaces $L_1 \subsetneq L_2 \subseteq \mathbb{K}^E$. Then every flat of $\mathcal{M}_{L_2}$ is a flat of $\mathcal{M}_{L_1}$, as the reader might be able to deduce. In light of this, given two matroids $\mathcal{M}$ and $\mathcal{N}$ on the same ground set $E$, one says that $\mathcal{N}$ is a lift of $\mathcal{M}$ if every flat of $\mathcal{N}$ is a flat of $\mathcal{M}$.

Finally, suppose we have a flag, i.e. a sequence of nested linear subspaces $L_1 \subsetneq \dots \subsetneq L_k \subseteq \mathbb{K}^E$. Then $\mathcal{M}_{L_{i+1}}$ is a lift of $\mathcal{M}_{L_i}$ for each $i$. Then, a sequence of matroids $\mathfrak{F} = (M_1,\dots,M_k)$ on the same ground set $E$ is called a flag matroid if $M_{i+1}$ is a lift of $M_i$ for each $i$. This implies that ${\rm rank}(M_i) < {\rm rank}(M_{i+1})$. If ${\rm rank}(M_{i+1}) = {\rm rank}(M_i) + 1$ for each $i$, then we say that $\mathfrak{F}$ is saturated. A flag matroid $\mathfrak{F}$ that can be expressed as $\mathcal{M}_{L_1},\dots,\mathcal{M}_{L_k}$ for a flag $L_1 \subsetneq \dots \subsetneq L_k$ of subspaces of a $\mathbb{K}$-vector space are called $\mathbb{K}$-representable and the corresponding sequence of linear spaces is called a $\mathbb{K}$-representation of $\mathfrak{F}$.

On a concrete level, a $\mathbb{K}$-representation of a flag matroid $\mathfrak{F} = (M_1,\dots,M_k)$ is a matrix $A \in \mathbb{K}^{r\times n}$ such that the first ${\rm rank}(M_i)$ rows of $A$ are a representation of $M_i$ for each $i$. For example, recall that $U_{r,n}$ denotes the uniform matroid of rank $r$ on $n$ elements and consider the flag matroid

$\mathfrak{F} = (U_{1,3},U_{2,3})$.

Then if $\mathbb{K}$ is a field with at least three elements, the following is a $\mathbb{K}$-representation of $\mathfrak{F}$

$\begin{pmatrix}1 & 1 & 1 \\ 0 & 1 & 2\end{pmatrix}$.

Note that if $\mathbb{K}$ is the field with two elements, then there is no $\mathbb{K}$-representation of $\mathfrak{F}$ even though both $U_{1,3}$ and $U_{2,3}$ are both $\mathbb{K}$-representable as matroids. Indeed, since the first row of such a matrix has to be a representation of $U_{1,3}$, this implies that the first row must be all ones, which will then imply that at least two of the columns are the same so the full matrix will not be a representation of $U_{2,3}$.

Given a field $\mathbb{K}$, one can ask: does there exist a “nice” characterization of the $\mathbb{K}$-representable flag matroids? Just as with matroids, we can do this by establishing a theory of minors for flag matroids, and then give a forbidden minor characterization. So far, we have been able to do this for saturated flag matroids that are representable over the fields with two and three elements.

Duals and Minors of flag matroids

The notions of deletion, contraction, and duality extend to flag matroids. Let $\mathfrak{F} = (M_1,\dots,M_k)$ be a flag matroid on ground set $E$. The dual of $\mathfrak{F}$, denoted $\mathfrak{F}^*$, is $(M_k^*,\dots,M_1^*)$ where $M^*$ denotes the dual of a matroid $M$. Given $e \in E$, we define the deletion and contraction $\mathfrak{F}\setminus e$ and $\mathfrak{F} / e$ by doing the corresponding operations on their constituent matroids, i.e.

$\mathfrak{F} \setminus e := (M_1 \setminus e, \dots, M_k \setminus e)$

and

$\mathfrak{F} / e := (M_1 /e, \dots, M_k / e)$.

If two constituent matroids become the same after deleting or contracting an element, we remove that matroid and reindex. Just as with matroids, contraction and deletion are dual operations, i.e.

$\mathfrak{F} / e = (\mathfrak{F}^*\setminus e)^*$.

Our theory of minors for flag matroids requires one more operation that does not have an analogue in the matroid setting. In particular, a flag matroid obtained from $\mathfrak{F}$ by removing a constituent matroid is called a chopping. Note that a chopping of a saturated flag matroid will only be saturated if the highest or lowest matroid is removed. Any flag matroid obtained from $\mathfrak{F}$ via a sequence of deletion, contraction, and chopping operations is called a minor of $\mathfrak{F}$.

Proposition. Let $\mathfrak{F}$ be a flag matroid and let $\mathbb{K}$ be a field. Then if $\mathfrak{F}$ is $\mathbb{K}$-representable, so is $\mathfrak{F}^*$ and any minor of $\mathfrak{F}$.

In principle, the above proposition allows us to characterize the class of $\mathbb{K}$-representable flag matroids by giving a list of minimally non-$\mathbb{K}$-representable minors. When $\mathbb{K}$ has two elements, we have the following forbidden minor characterization of the $\mathbb{K}$-representable flag matroids.

Theorem: Let $\mathfrak{F}$ be a saturated flag matroid. Then $\mathfrak{F}$ is representable over the two-element field if and only if $\mathfrak{F}$ has no minors of the form $(U_{1,3},U_{2,3})$ or $U_{2,4}$.

We also have a forbidden-minor characterization for the saturated flag matroids that are representable over the field with three elements. We use the notation $F_7$ to denote the fano matroid and $F_7^*$ to denote its dual.

Theorem: Let $\mathfrak{F}$ be a saturated flag matroid. Then $\mathfrak{F}$ is representable over the three element field if and only if $\mathfrak{F}$ has no minors of the form $R$ or $(R/e, R \setminus e)$ where $R \in \{U_{2,5},U_{3,5},F_7,F_7^*\}$.

Within the next week or two, we hope to have our preprint on the arXiv, so stay tuned! Flag matroids are an interesting and potentially quite fruitful line of research for matroid theorists, as many of the same questions about representability can be asked.

Colouring and list-colouring

Staying close in theme to last month’s post, this month I’m writing about decomposing matroids into independent sets.

The colouring number (or covering number), $\text{col}(M)$ of a matroid $M$ is defined as the smallest $t$ for which the ground set of $M$ can be partitioned into $t$ independent sets. I’ve written before about how I like the term colouring number since it highlights the analogy with the chromatic number of graphs (which is the smallest number of vertex-independent sets in which the graph can be partitioned). For this blog post, though, it is more illuminating to compare the colouring number to the edge-chromatic number of a graph.

The chromatic number for graphs has many variations that are studied for their own sake, such as the list-chromatic number. Similarly, there is a list-colouring version of the colouring number, which is defined as follows.

Definition. Let $M$ be a loopless matroid, and suppose that for each element $e$ of $M$ we are given a list $L(e)$ of colours available to element $e$. An $L$-colouring of $M$ is a function $c$ that maps each element $e$ of $M$ to an element of $L(e)$, with the additional property that $c^{-1}(i)$ is an independent set of $M$ for all $i \in \bigcup_{e} L(e)$. The matroid $M$ is $k$-list-colourable if it has an $L$-colouring whenever $|L(e)| \ge k$ for each $e$. We write $\text{col}_\ell(M)$ for the smallest $k$ such that $M$ is $k$-list-colourable.

When $L(e) = \{1,2,\ldots,k\}$ for each $e$, $L$-colouring corresponds to colouring the matroid with $k$ colours. This implies that $\text{col}_\ell(M) \ge \text{col}(M)$. For graphs the gap between chromatic number and list-chromatic number can be arbitrarily large. Surprisingly, the colouring and list-colouring numbers for matroids are equal, as shown by Seymour (using an application of matroid union!).

Theorem (Seymour). $\text{col}_\ell(M) = \text{col}(M)$ for all loopless matroids $M$.

It is clear from this theorem that nothing is to be gained by considering the list-colouring problem for matroids instead of the colouring problem.

However, it is not known if an analogue of Seymour’s result holds for matroid intersections. Let $M_1$ and $M_2$ be two matroids on a common ground set $E$. The colouring number $\text{col}(M_1 \wedge M_2)$ is the smallest $t$ for which $E$ can be partitioned into $k$ sets that are independent in both $M_1$ and $M_2$ (here, $M_1 \wedge m_2$ refers to the matroid intersection of $M_1$ and $M_2$). The list-colouring number for $\chi_\ell(M_1 \wedge M_2)$ is similarly obtained as a generalisation of the list-colouring number for matroids.

As in the case of (list-)colouring matroids, a straightforward argument shows that $\text{col}_\ell(M_1 \wedge M_2) \ge \text{col}(M_1 \wedge M_2)$, but it is not known if equality holds for all matroid intersections.

1-partition matroids and Galvin’s theorem

A 1-partition matroid is a matroid whose ground set can be partitioned into subsets such that the independent sets of the matroid contain at most one element from each of the subsets. In other words, a loopless matroid $M$ is a 1-partition matroid if and only if it is the direct sum of $r(M)$ parallel classes.

Such matroids arise naturally in matching theory. A bipartite graph $G$ with bipartition $L \cup R$ comes with two 1-partition matroids on $E$: one in which the parallel classes are formed by the edges incident with each of the vertices in $L$, and one whose parallel classes similarly correspond to the vertices in $R$. In fact, the matchings of $G$ are precisely the common independent sets of these two matroids.

Galvin showed that the list-edge-chromatic number and the edge-chromatic number of bipartite graphs coincide, which is equivalent to the following result.

Theorem (Galvin). $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$ for all loopless 1-partition matroids.

It is natural to ask if the conclusion of the theorem still holds when the 1-partition matroids are replaced by matroids that are the direct sum of uniform matroids whose rank may be larger than 1 (such matroids are called partition matroids). It turns out that the answer is ‘yes’, a result that was proved only a few months ago by Guo.

Theorem (Guo). $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$ for all loopless partition matroids.

When is $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$?

In light of Seymour’s theorem for the list-colouring number of matroids and the above results by Galvin and Guo, it is tempting to ask whether the list-colouring number is always equal to the colouring number for matroid intersections – as Király did.

Question (Király). Is it always true that $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$?

Very little appears to be known about this problem, with the exception of the results by Galvin and Guo and the following result by Király and Pap.

Theorem (Király and Pap). $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$ in each of the following cases:

• $M_1$ and $M_2$ are both transversal matroids; or
• $M_1$ is the graphic matroid and $M_2$ is the 1-partition matroid whose parts are formed by the in-stars of the graph that is the union of two arborescences with the same root; or
• $M_1$ and $M_2$ both have rank 2.

(The third case of of their result actually extends to the situation where $M_1$ is a rank-2 matroid and $M_2$ is an arbitrary matroid.)

As a step towards resolution of Király’s question, the following problem may be more accessible:

Question. Is it true that $\text{col}_\ell(M_1 \wedge M_2) = \text{col}(M_1 \wedge M_2)$ for all loopless rank-3 matroids $M_1$ and $M_2$?