A theory of q-transversals

This is a guest post by Mark Saaltink.

A $q$-analog is formed by replacing the notion of a set by the notion of a vector space, with a corresponding replacement of other concepts: cardinality becomes dimension, elements are replaced by 1-dimensional subspaces, the empty set is replaced by the 0-dimensional subspace, intersection remains the same, and union is replaced by sum. (It is not always clear how to replace set difference or symmetric difference.) The application of this idea to matroid theory gives the theory of q-matroids [Jur2018][Cer2022], which Relinde Jurrius has described in this forum, most recently with the analog of delta-matroids. In this post I’ll define a $q$-analog of a transversal [Mir1971], and show that there is still a connection with matroids, as well as analogs of many of the main theorems of transversal theory. A more complete account has been posted on arXiv.

$q$-matroids, briefly

A $q$-matroid can be characterized by its bases, independent sets, circuits, or spanning sets, but the simplest definition for our purposes is via the rank function.

Definition 0. Let $V$ be a vector space and ${\cal L}(V)$ be the lattice of subspaces of $V$. A $q$-matroid on $V$ is determined by a rank function $r: {\cal L}(V) \rightarrow \mathbb{Z}$, satisfying, for all $A, B \in {\cal L}(V)$,

  1. $0 \leq r(A) \leq \dim A$ (rank is non-negative and bounded by dimension),
  2. if $A \leq B$ then $r(A) \leq r(B)$ (rank is non-decreasing), and
  3. $r(A \vee B) + r(A \wedge B) \leq r(A) + r(B)$ (rank is submodular).

The usual concepts of matroid theory apply equally well to $q$-matroids: a subspace $A$ is independent if $r(A) = \dim A$, and dependent otherwise; a subspace $A$ is a circuit if it is dependent but all its proper subspaces are independent; the closure of $A$ is the largest subspace $B$ with $A \leq B \leq V$ and $r(B) = r(A)$; and $A$ is spanning if its closure is $V$. Axiom systems for $q$-matroids in terms of independent sets, bases, or circuits can be found in [Cer2022].

The closure of the trivial subspace $\{ 0 \}$ gives the so-called loop space of the matroid; any subspace of rank 0 is contained in this loop space. A $q$-matroid of rank 1 is therefore completely characterized by its loop space $L$, with the rank of a subspace $X$ being 0 if it is a subspace of $L$ and 1 otherwise.

A large class of $q$-matroids can be defined algebraically; these are the representable $q$-matroids. Given some $n\times m$ matrix $G$ over a field $K$ extending $\mathbb{F}_q$, we can define the $q$-matroid represented by $G$ as follows: if a subspace of $\mathbb{F}_q^m$ is the row space of matrix $X$, then its rank in the $q$-matroid is the rank of $GX^T$. It can be seen that this does not depend on the matrix $X$ we use; if $X$ and $Y$ are full-rank matrices with equal row spans, then there is some invertible matrix $A$ so that $Y = AX$. Then $GY^T = GX^TA^T$, and as $A^T$ is invertible, the ranks are the same. Note that the entries of $G$ may lie in a larger field than the vector space is defined over. Usually $K$ is equal to $\mathbb{F}_{q^k}$ for some $k$.

Unlike a normal matroid that might be representable over fields of many different characteristics, a $q$-matroid representation has its characteristic fixed by the vector space the $q$-matroid is defined on. I suppose the interesting question about representations is then which extension fields are possible.

Normal transversals, abnormally

To have a clear connection to $q$-matroids, it seems to work best to analogize a cryptomorphic version of transversal theory. Where the usual definition has membership, this definition uses non-membership.

Definition Given an indexed family ${\cal X} = (X_1,X_2, \dotsc, X_n)$ of subsets of some given set $S$, an avoiding transversal of $\cal X$ is a set of elements $x_1, x_2, \dotsc, x_n$ of $S$, all distinct, with each $x_i \notin X_i$. A partial avoiding transversal of $\cal X$ is an avoiding transversal of some subfamily (that is, containing some subset of the $X_i$).

Clearly, when $A_i = S \setminus X_i$, an avoiding transversal of $\cal X$ is just a transversal of the $A_i$.

The main properties of transversals can be recast in this setting. We first define ${\cal X}(J) = \bigcap_{j\in J} X_j$ for any $J \subseteq \{1, 2, \dots,n\}$, with the convention ${\cal X}(\emptyset) = S$.

Theorem

  1. (Hall) $\cal X$ has a transversal iff for all $J \subseteq \{1, 2, \dots,n\}$ we have $|{\cal X}(J)| + |J| \leq |S|$.
  2. (Rado) Suppose $M$ is a matroid on $S$ with co-nullity function $\nu^*$. $\cal X$ has a transversal that is independent in $M$ iff for all $J \subseteq \{1, 2, \dots,n\}$ we have $\nu^*({\cal X}(J)) + |J| \leq \nu^*(S)$.
  3. (Edmonds and Fulkerson) The set of partial transversals of $\cal X$ are the independent sets of a matroid.
  4. (Piff and Welsh) Transversal matroids are representable over every sufficiently large field.
  5. A matroid is transversal iff it is the union of a collection of rank-1 matroids.

When $M$ is the matroid whose independent sets are the partial avoiding transversals of $\cal X$ we say that $M$ is a transversal matroid and $\cal X$ is a co-presentation of $M$. Co-presentations have some nice properties:

  1. If the rank of transversal matroid $M$ is $r$, then $M$ has a co-presentation with $r$ elements.
  2. If $\cal X$ is a co-presentation of $M$ and the rank of $M$ is $r$, then $\cal X$ has a subfamily with $r$ elements that is also a co-presentation of $M$.
  3. If $(X_1, \dots, X_r)$ is a co-presentation of $M$, then each $X_i$ is a flat.
  4. If $M$ is a transversal matroid, then it has a unique minimal co-presentation, where a co-presentation is minimal if no members can be removed or replaced by strictly smaller sets while still co-representing $M$.

$q$-transversals, finally

In this section we will be talking about the vector space $V$ and its subspaces as well as $q$-matroids, so there is room for some confusion when we say “independent” or “basis”. Therefore we will qualify these terms and speak of a “vector basis” or “independent vectors” when referring to $V$ and its elements, or a “matroid basis” or “independent subspace” when referring to aspects of a $q$-matroid.

Definition Let a vector space $V$ be given, together with a family ${\cal X} = (X_1, \dotsc, X_n)$ of subspaces of $V$. A $q$-transversal is a dimension $n$ subspace $T$ of $V$ where every vector basis $B$ of $T$ has an ordering $B = \{b_1, \dots, b_n\}$ such that $b_i \notin X_i$ for $i \in\{1,2,\dotsc,n\}$. That is, every vector basis of $T$ is an avoiding transversal of $\cal X$. A partial $q$-transversal is a dimension $n$ subspace $T$ where every vector basis of $T$ is a partial avoiding transversal of $\cal X$.

The definition of partial $q$-transversal deserves some note. It would be more analogous to the conventional theory to declare a partial $q$-transversal to be a $q$-transversal of some subsystem of $\cal X$. This turns out to be equivalent, but is more difficult to work with. Analogs of the major properties of transversals are also enjoyed by $q$-transversals as defined this way:

Theorem

  • Family $\cal X$ has a $q$-transversal iff for every nonempty $J \subseteq \{1, 2, \dots, n\}$ we have $\dim {\cal X}(J) + |J| \leq \dim V$.
  • The set of partial $q$-transversals of a family form the independent subspaces of a $q$-matroid.
  • A $q$-matroid is $q$-transversal iff it is the union of a collection of rank 1 $q$-matroids.

I conjecture that all $q$-transversal matroids are representable, but have only proven a special case where the spaces $X_i$ align is a particular way:

Theorem Suppose that $V$ has a vector basis $\{b_1, b_2, \dotsc, b_n\}$ so that each of the $X_i$ has the form $X_i = \left< b_i \,|\, i \in L_i \right>$ for some sets $L_i \subseteq \{1, 2, \dots, n \}$. Then the associated $q$-transversal matroid is representable.

I also conjecture that an analog of Rado’s theorem holds. Recall that if $\cal B$ is the set of bases of matroid $M$, then co-nullity satisfies $\nu^*(X) = \min_{B \in \cal B} | B \cap X |$, so we may plausibly define a $q$-analog $\bar n$ satisfying $\bar n(X) = \min_{B \in \cal B} \dim(B \wedge X)$ for a $q$-matroid $M$ with bases $\cal B$.

Conjecture Suppose $M$ is a $q$-matroid on vector space $V$, with rank function $r$, and $\cal X$ is a system of subspaces of $V$. Then $\cal X$ has a $q$-transversal that is independent in $M$ iff for all $J \subseteq I$ we have $\bar n ({\cal X}(J)) + |J| \leq \bar n (V)$.

When $M$ is the $q$-matroid whose independent spaces are the set partial $q$-transversals of a family $\cal X$ we say that $M$ is $q$-transversal and that $\cal X$ is a presentation of $M$.

  1. If the rank of $q$-transversal matroid $M$ is $r$, then $M$ has a presentation with $r$ elements.
  2. If $\cal X$ is a presentation of $q$-matroid $M$ and the rank of $M$ is $r$, then $\cal X$ has a subfamily with $r$ elements that is also a presentation of $M$.
  3. If $(X_1, \dots, X_r)$ is a presentation of $M$, then each $X_i$ is a flat.

I conjecture that any $q$-transversal matroid has a unique minimal presentation.

As can be seen, while there are still some interesting questions to be settled, the analogy with normal transversal theory looks promising. Details and proofs are in the paper on arXiv [Saa2025].

References

[Cer2002] Michela Ceria and Relinde Jurrius. Alternatives for the $q$-matroid axioms of independent spaces, bases, and spanning spaces. arXiv.org/abs/2207.07324v3, December 2022.

[Jur2018] Relinde Jurrius and Ruud Pellikaan. Defining the $q$-analog of a matroid. Article #P3.2, The Electronic Journal of Combinatorics 25(3), 2018.

[Mir1971] Leon Mirsky. Transversal Theory: an account of some aspects of combinatorial mathematics. Academic Press, 1971.

[Saa2025] Mark Saaltink. A theory of $q$-transversals arXiv.org/abs/2503.12201, March 2025.

Greedy strikes back: A 4.75-competitive algorithm for the laminar matroid secretary problem

This is a guest post by Zahra Parsaeian. This post is a follow-up to Tony Huynh’s 2015 blog post of the matroid secretary problem, focusing on the special case of laminar matroids. Zahra highlights the last decade’s steady progress in this special case and outlines the recent greedy algorithm that brings the competitive ratio down to 4.75.

From Secretaries to Laminar Matroids

The classical secretary problem asks for a strategy that hires (with high probability) the best of $n$ applicants who appear in uniformly random order. The well-known threshold strategy—observe the first $n/e$ applicants, then pick the first candidate better than all previous ones—achieves a competitive ratio of $e$.

The matroid secretary problem (MSP), introduced by Babaioff, Immorlica & Kleinberg (2007), generalises this set-selection game: instead of choosing a single element, we must pick an independent set of elements in an (unknown) weighted matroid that arrive online. The grand conjecture is that every matroid admits an $O(1)$-competitive algorithm.

A particularly structured—and surprisingly rich—family of matroids is the laminar matroids. Here the ground set $E$ is organised by a laminar family $\mathcal{F}$ (any two sets are either disjoint or nested), and each $B \in \mathcal{F}$ comes with a capacity $c(B)$; a subset $S \subseteq E$ is independent if $|S \cap B| \leq c(B)$ for every $B$. Partition matroids are the simplest laminar matroids, but many “hierarchical quota” constraints in practice are laminar as well.

Why single them out? Laminar matroids already capture the core difficulty of MSP while admitting extra structure that can be exploited algorithmically.

A Decade of Improving Constants

Tony’s 2015 survey listed Im & Wang’s first constant-competitive algorithm (competitive ratio $\approx 5333.33$). Since then the record book has been rewritten multiple times:

YearAuthorsTechniqueCompetitive ratio
2011Im & WangReduction to partition + “sample and price” $16000/3 \approx 5333.33$
2013Jaillet, Soto & ZenklusenImproved reduction$\sqrt{3e} \approx 14.12$
2016Ma, Tang & WangSimulated greedy9.6
2018Soto, Turkieltaub & VerdugoForbidden sets$3\sqrt{3} \approx 5.196$
2024Huang, Parsaeian & ZhuPlain greedy4.75
2024Bérczi, Livanos, Soto & VerdugoLabeling scheme (tight)$1/(1 – \ln 2) \approx 3.257$

Progress has come from increasingly delicate analyses, often accompanied by algorithmic complexity. The latest result is a counter-trend: a simpler algorithm with a better constant.

Greedy—But With Better Timing

Before we describe the algorithm, recall the standard arrival model: each element independently receives a uniformly random arrival time in $[0,1]$, yielding a random order of appearance that our online algorithm must process.

Our algorithm really is the textbook greedy rule, decorated with a single time threshold $t_0$.

  • Sampling phase. Ignore all elements that arrive before time $t_0$ (we use $t_0 = 0.7$).
  • Selection phase. When an element $e$ arrives at time $t > t_0$, inspect the elements seen so far. If $e$ belongs to the offline optimum of the already-arrived instance and adding it keeps the set independent, accept it.

That is all! There are no prices, buckets, or recursive calls—just a look-ahead greedy algorithm.

Why does it work? Greedy alone is not new: the 9.6-competitive algorithm of Ma et al. also used greedy, but their acceptance rule only looked at the sample window. The key novelty is to test membership in the current optimum, which becomes increasingly selective as more elements arrive.

The analysis hinges on two observations:

  • Independence of arrival times. Viewing arrival times as i.i.d. uniform variables decouples the combinatorial structure from time.
  • Order statistics $\rightarrow$ Gamma distribution. For each laminar constraint $B$, the arrival gap between its last $c(B)$ optimal elements behaves like a Gamma-distributed random variable. Bounding the tail of this distribution shows that every optimal element survives with probability $\geq 1/4.75$.

The final ratio is therefore 4.75-probability-competitive, which also implies 4.75-utility-competitive. Moreover, the algorithm operates in the ordinal model (it only needs relative weight rankings), aligning with applications where exact weights are costly to elicit.

Greedy’s limit: the 3.257 barrier

Bérczi et al. recently introduced a labeling scheme framework and proved that the best achievable competitive ratio for any greedy algorithm on laminar matroids is $\frac{1}{1 – \ln 2} \approx 3.257$. This is tight: they present a greedy variant that achieves it, and show no greedy algorithm can do better.

How close are we to “optimal”?

Laminar matroids remain the most complex class with a known constant. A natural next step is to sharpen the constant—can we reach the golden goal of $e$? On the structural side, extending the greedy-with-look-ahead idea to regular or binary matroids looks tantalising (the last conjecture in Tony’s post is still wide open). The recent structure theorems for minor-closed classes may reopen that door.

Takeaways

  • Simplicity can win. A one-line greedy rule beats a sophisticated forbidden-sets construction.
  • Timing matters. The 0.7 threshold balances the risk of sampling versus missing high-value elements.
  • Open questions abound. Improving the constant for laminar matroids (or proving a lower bound!), and generalising to wider matroid families, remain fertile ground.

I hope this short note complements Tony’s earlier exposition and sparks fresh interest in the laminar MSP. Feedback, questions, and ideas are most welcome—please share them in the comments or reach out directly.

This post was updated on May 26, 2025 to include the result in the recent Bérczi et al. paper.

Matroids of large girth

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.)

Matroid Basis Density

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.

Figure 1: 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.