The girth of a matroid $M$ is the minimum size of a circuit of $M$, or $\infty$ if $M$ has no circuits. There are some uninteresting matroids of large girth: the uniform matroids $U_{t,t}$ and $U_{t-1, t}$, which are the graphic matroids of forests and cycles. However, these matroids are not cosimple; their duals contain loops or parallel pairs. Can we say anything more interesting about cosimple matroids of large girth?

Question 1: What are the unavoidable minors in cosimple matroids of large girth?

Thomassen [4] answered this question in the graphic case by showing that, surprisingly, every graph is unavoidable. A graphic matroid $M(G)$ is cosimple if and only if $G$ is $3$-edge-connected, that is, $G$ cannot be disconnected by deleting at most two edges.

Theorem 2 (Thomassen): There is a function $f$ so that for every integer $t$, every $3$-edge-connected graph of girth at least $f(t)$ contains the clique $K_t$ as a minor.

The cographic case is equivalent to a well-known theorem of Mader [3] about the average degree of graphs with a forbidden minor.

Theorem 3 (Mader): There is a function $f$ so that for every integer $t$, every cosimple cographic matroid of girth at least $f(t)$ contains $M(K_t)^*$ as a minor.

So in general we must forbid both a graphic and a cographic matroid. (There exist both graphic and cographic matroids which are cosimple and have large girth.) Geelen, Gerards, and Whittle [2] conjectured that this necessary condition is also sufficient for $GF(q)$-representable matroids. James Davies, Meike Hatzel, Kolja Knauer, Torsten Ueckerdt, and I recently proved this conjecture. The paper is out on arXiv [1].

Theorem 4 (Davies, Hatzel, Knauer, McCarty, Ueckerdt): There is a function $f$ so that for every integer $t$ and finite field $GF(q)$, every cosimple $GF(q)$-representable matroid of girth at least $f(t,q)$ contains either $M(K_t)$ or $M(K_t)^*$ as a minor.

The proof relies on interpreting the Growth Rate Theorem in terms of the shatter function of an associated set system. This allows us to use tools from the combinatorics of set systems. Many of these tools are very powerful, and yet (as far as I know), this is the first application of such tools to matroid theory. See the paper for details.

The next step would be to prove a stronger version of Theorem 4 with a line $U_{2, q+2}$ and a coline $U_{q, q+2}$ forbidden instead of the requirement about $GF(q)$-representability. The coline $U_{q, q+2}$ is a cosimple matroid of large girth. However, it is less satisfying to forbid a line since it contains short circuits.

If we do not want to forbid a line, then we must forbid a bicircular matroid. This is because there exist cosimple bicircular matroids of large girth, and for sufficiently large $t$ they do not contain $U_{t, t+2}$, $M(K_t)$, or $M(K_t)^*$ as a minor. We (rather boldly) conjecture that these are the only unavoidable cosimple matroids of large girth. Let us write $B(G)$ for the bicircular matroid of a graph $G$.

Conjecture 5 (Davies, Hatzel, Knauer, McCarty, Ueckerdt): There exists a function $f$ such that for every integer $t$, every cosimple matroid with girth at least $f(t)$ contains either $U_{q, q+2}$, $M(K_t)$, $M(K_t)^*$, or $B(K_t)$ as a minor.

 

References:

[1] Davies, Hatzel, Knauer, McCarty, Ueckerdt. Girth in $GF(q)$-representable matroids. ArXiv: 2504.21797, 2025.

[2] Geelen, Gerards, and Whittle. The highly connected matroids in minor-closed
classes. Ann. Comb., 19(1):107–123, 2015.

[3] Mader. Homomorphieeigenschaften und mittlere Kantendichte von Graphen.
Math. Ann., 174:265–268, 1967.

[4] Thomassen. Girth in graphs. J. Combin. Theory Ser. B, 35(2):129–141, 1983.

(Note: The theorem Thomassen proved might seem stronger at first glance since he just assumed the graph has minimum degree at least $3$. However, it is possible to reduce this theorem to the $3$-edge-connected case.)

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.