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.

Flag Matroids

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.

A $q$-analogue of delta-matroids

This post is based on joint work with Michela Ceria and Trygve Jonsen.

It was already four years ago that I wrote about the q-analogue of a matroid. Over these years, there have been a lot of developments in this area. A non-exhaustive list: a lot of cryptomorphisms of q-matroids have been proven [BCJ22], the direct sum has been defined (this is less trivial than it sounds!) [CJ24], there are hints of category theory [GJ23], and the representability of q-matroids has been translated to the finite geometry problem of finding certain linear sets [AJNZ24+].

In this post, I’ll talk about the q-analogue of delta-matroids. You might remember them from this choose-your-own-adventure post from Carolyn Chun. But first, let’s develop some intuition for the q-analogue of a matroid.

In combinatorics, when we talk about a q-analogue, we mean a generalisation from sets to finite dimensional vector spaces (often over a finite field). A straightforward definition of a q-matroid can be given in terms of its rank function:

Definition. A q-matroid is a pair $(E,r)$ of a finite dimensional vector space $E$ and an integer-valued function $r$ on the subspaces of $E$ such that for all $A,B\subseteq E$:
(r1) $0\leq r(A)\leq\dim(A)$.
(r2) If $A\subseteq B$ then $r(A)\leq r(B)$.
(r3) $r(A+B)+r(A\cap B)\leq r(A)+r(B)$ (semimodularity)

Here we see that the role of the cardinality of a set is replaced by that of a dimension of a space. Inclusion and intersection are defined as one would expect, and the role of elements of a set is played by 1-dimensional subspaces in the q-analogue. The q-analogue of the union of sets is the sum of vector spaces. Here we see the first difference between the world of sets and that of spaces: where the union of sets $A$ and $B$ contains only elements that are either in $A$ or in $B$, the sum $A+B$ of vector spaces $A$ and $B$ contains a lot of 1-dimensional spaces that were in neither $A$ nor $B$. Luckily, we have semimodularity of the rank function to keep control over all these new spaces.

Lemma. Loops come in spaces.

A loop is a 1-dimensional space of rank 0. If $x$ and $y$ are loops, then by semimodularity, all 1-dimensional subspaces of $x+y$ are loops. The opposite of this result is the following.

Corollary. Independent spaces never come alone.

Suppose a q-matroid $(E,r)$ has a 1-dimensional independent space $x$. Then this q-matroid might have loops, but we know that the space $L$ containing exactly all loops (let’s call it the loop space) can have dimension at most $\dim(E)-1$, since $x$ is not a loop. But if $L$ has dimension $\dim(E)-1$, it means that all 1-dimensional spaces that are not in $L$, are independent. And there are many of them!

This reasoning motivates the definition of a q-matroid in terms of its bases [CJ24a,CJ24b]. (This definition is cryptomorphic to the one above: define a basis as a subspace such that $r(B)=r(E)$, and for the other way around, let $r(A)$ be the dimension of the biggest intersection between $A$ and a basis.)

Definition. A q-matroid is a pair $(E,\mathcal{B})$ of a finite dimensional vector space $E$ and a family $\mathcal{B}$ of subspaces of $E$ such that:
(B1) $\mathcal{B}\neq\emptyset$.
(B2) For all $B_1,B_2\in\mathcal{B}$ we have $\dim B_1=\dim B_2$.
(B3) For all $B_1,B_2\in\mathcal{B}$, and for each subspace $A$ that has codimension 1 in $B_1$ there exists $X\subseteq E$ of codimension 1 in $E$ such that $X \supseteq A$, $X\not \supseteq B_2$ and $A+x \in \mathcal{B}$ for all 1-dimensional $x\subseteq E$, $x\not\subseteq X$.

(B1) and (B2) should not surprise you, but (B3) looks at first sight rather different from its classical counterpart. But let us translate the classical axiom a bit. We start with a basis and remove an element from it. This is the same as saying we take a subset of $B_1$ of size $|B_1|-1$. Then, we add an element from a basis $B_2$ that is not in $B_1$. In a convoluted way, this can be seen as first taking a subset $X$ of $E$ of size $n-1$ that does not contain $B_2$, and then adding the complement of $X$ in $E$ to $B_1$. However, this convoluted view does give us a statement of which the q-analogue is exactly (B3) above. Note as well that (B3) produces a lot of new bases, not just one: this is due to the fact that independent spaces never come alone.

Let us now move to delta-matroids. The definition we are going to use to make a q-analogue, is the following.

Definition. A delta-matroid is a pair $(E,\mathcal{F})$ of a finite set $E$ and a nonempty family $\mathcal{F}$ of subsets of $E$ such that for all $X,Y\in\mathcal{F}$ and for all $x\in X\triangle Y$ there is a $y\in X\triangle Y$ such that $X\triangle\{x,y\}\in\mathcal{F}$.

This definition makes use of the symmetric difference and unfortunately, we have no clue how a well-defined q-analogue of the symmetric difference looks like. (Ideas are welcome!) However, we can split this definition in four cases, depending on whether $x$ and $y$ are in $X-Y$ or in $Y-X$.

We can now make a q-analogue of a delta-matroid by treating all these four cases separately [CJJ24+].

Definition. A q-delta-matroid is a pair $(E,\mathcal{F})$ of a finite space $E$ and a nonempty family $\mathcal{F}$ of subsets of $E$ such that:
(F1) For every two subspaces $X$ and $Y$ in $\mathcal{F}$, and for each subspace $A\subseteq E$ that has codimension 1 in $X$, there either exists:
    (i) a codimension 1 space $Z \subseteq E$ with $A \subseteq Z$ and $Y\not\subseteq Z$, such that for all 1-dimensional $z\subseteq E$, $z\not\subseteq Z$ it holds that $A+z\in \mathcal{F}$; or
    (ii) a codimension 1 space $Z\subseteq E$ such that $Z \cap A \in \mathcal{F}$.
(F2) For every two subspaces $X$ and $Y$ in $\mathcal{F}$, and for each subspace $A\subseteq E$ with $X$ of codimension 1 in $A$, there either exists:
    (iii) a 1-dimensional $z\subseteq E$ with $z \subseteq A$, $z\not\subseteq Y$, such that for each $Z\subseteq E$ of codimension 1, $z\not\subseteq Z$ it holds that $A \cap Z \in \mathcal{F}$; or
    (iv) a 1-dimensional $z\subseteq E$ such that $A+z \in \mathcal{F}$.

The four cases of this definition reflect the four cases in the picture above, respectively. Note also the similarity between part (i) and (iii) and the basis axiom (B3). Just as in the classical case, a q-delta-matroid can be viewed as “take a q-matroid and forget that all bases need to have the same dimension”.

Here is an example of a q-delta-matroid. One can verify that this is indeed a q-delta-matroid by checking the definition above for every combination of dimensions of feasible spaces.

Example. Let $E=\mathbb{F}^4$ and $\mathcal{S}$ a spread of 2-spaces in $E$. (That is: a family of trivially intersecting 2-spaces such that every element of $E$ is in exactly one member of the spread.) Let $\mathcal{F}=\mathcal{S}\cup\{0,E\}$. Then $(E,\mathcal{F})$ is a q-delta-matroid.

The definition of a q-delta-matroid has some nice properties. First off: duality.

Theorem (dual q-delta-matroid). Let $(E,\mathcal{F})$ be a q-delta-matroid and let $\mathcal{F}^\perp=\{F^\perp:F\in\mathcal{F}\}$. Then $(E,\mathcal{F}^\perp)$ is a q-delta-matroid.

This statement follows immediately from the definition, since taking orthogonal complements in (F1) gives (F2) and vice versa. For delta-matroids there is also a notion of partial duality, also known as twist duality. We did not manage to find a q-analogue of this, largely due to the lack of q-analogue for the symmetric difference. Another concept that annoyingly does not have a straightforward q-analogue, is taking minors (via restriction and contraction) of q-delta-matroids. But for some positive news: we can make q-matroids from q-delta-matroids, and the other way around. The proofs of this statement are by directly checking the axioms.

Theorem (q-matroids from q-delta-matroids). Let $D=(E,\mathcal{F})$ be a q-delta-matroid. Then all feasible spaces of maximal dimension, and all feasible spaces of minimum dimension, are the families of bases of q-matroids. We call these the upper- and lower q-matroid of $D$.

Theorem (q-delta-matroids from q-matroids). The families of bases, independent spaces, and spanning spaces of a q-matroid all form the family of feasible spaces of a q-delta-matroid.

A much more involved result on q-delta-matroids has to do with strong maps. As in the classical case, a strong map between q-matroids is a linear map between their ground spaces where the inverse image of a flat is a flat. This leads to the definition of a qg-matroid:

Definition. Let $\varphi:M_1\to M_2$ be a strong map between q-matroids. Then the family of all spaces contained in a basis of $M_1$ and containing a basis of $M_2$, are the feasible spaces of a q-g-matroid.

Theorem. Every qg-matroid is a q-delta-matroid.

The inverse of this statement is not true: see the example above that is a q-delta-matroid but not a qg-matroid, since no 1-space or 3-space is a feasible space. We do see in this example that there is a strong map between the upper q-matroid, which is $U_{4,4}$, and the lower q-matroid $U_{0,4}$. We expect this to hold in general.

Conjecture. There is a strong map between the upper- and lower q-matroid of a q-delta-matroid.

This statement was proven in the classical case via the theory of multimatroids, a concept that does not seem to have a clear q-analogue (yet). We have some hope that the birank of a q-delta-matroid (of which I’ll skip the definition) might help with this goal.

Of course, our dream is to make a q-analogue of every equivalent definition of delta-matroids. That will not be easy, because it is at the moment pie in the sky to consider a q-analogue of ribbon graphs, or embeddings of graphs — we don’t even understand yet what the q-analogue of a graph is! However, there are several more direct questions, as mentioned along the way in this post, that are waiting for interested researchers to tackle them.

References

[AJNZ24+] Gianira N. Alfarano, Relinde Jurrius, Alessandro Neri, Ferdinando Zullo, Representability of the direct sum of uniform q-matroids (2024). Preprint, arXiv:2408.00630.

[BCJ22] Eimear Byrne, Michela Ceria, Relinde Jurrius, Constructions of new q-cryptomorphisms, Journal of Combinatorial Theory, Series B, 153 (2022), pp. 149–194.

[CJ24] Michela Ceria, Relinde Jurrius, The direct sum of q-matroids. Journal of Algebraic Combinatorics, 59 (2024), pp. 291–330.

[CJ24a] Michela Ceria, Relinde Jurrius, Alternatives for the q-matroid axioms of independent spaces, bases, and spanning spaces, Advances in Applied Mathematics, 153 (2024), 102632.

[CJ24b] Michela Ceria, Relinde Jurrius, Corrigendum to Alternatives for the $q$-matroid axioms of independent spaces, bases, and spanning spaces [Adv. Appl. Math. 153 (2024) 102632] Advances in Applied Mathematics 158 (2024), 102708.

[CJJ24+] Michela Ceria, Relinde Jurrius, Trygve Johnsen, A q-analogue of $\Delta$-matroids and related concepts (2024). Preprint, arXiv:2406.14944.

[GJ23] Heide Gluesing-Luerssen, Benjamin Jany, Coproducts in categories of q-matroids, European Journal of Combinatorics, 112 (2023), 103733.

List-colouring matroid intersections

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$?