Author Archives: Relinde Jurrius

Direct sum of q-matroids

Posted on by
Reply

One of the most straightforward operations you can do when you want to make a new matroid out of old ones, is taking the direct sum. The direct sum of the matroids $M_1=(E_1,r_1)$ and $M_2=(E_2,r_2)$ is the matroid $M$ on ground set $E=E_1\sqcup E_2$ with for all $A\subseteq E$,
\[ r(A)=r_1(A\cap E_1)+r_2(A\cap E_2). \]Alternatively, its independent sets are the unions of an independent set in $M_1$ and an independent set in $M_2$. The third equivalent way to define the direct sum is by saying that $M=M_1\oplus M_2$ is precisely the matroid such that $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$.

In this post, we will discuss the q-analogue of this concept. The q-analogues of matroids, called q-matroids, have been introduced here. Instead of considering a matroid on a finite ground set, where every subset has a rank that satisfies certain axioms, we take a q-matroid on a finite dimensional vector space where every subspace has a rank, again satisfying certain axioms. A good intuition is to think about matroids as a bicolouring of the Boolean lattice, and q-matroids as a bicolouring of the subspace lattice.

If we take the direct sum of two q-matroids $M_1=(E_1,r_1)$ and $M_2=(E_2,r_2)$, it makes sense for $M=M_1\oplus M_2$ to have as a ground space the direct sum of vector spaces $E_1\oplus E_2$. It is also reasonable to ask that $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$. But then it gets difficult. Where for sets, we can write any subset $A\subseteq E_1\sqcup E_2$ as $(A\cap E_1)\sqcup(A\cap E_2)$, such a thing is not true for vector spaces. Suppose for example $E_1=\langle100\rangle$ and $E_2=\langle010,001\rangle$ (over my favourite finite field $\mathbb{F}_2$) such that $E_1\oplus E_2$ is a 3-dimensional space. Then the space $A=\langle111\rangle$ does not intersect $E_1$ nor $E_2$. What is its rank going to be?

One could hope that maybe the rank axioms of q-matroids take care of this. Look for example at the direct sum of $U_{1,1}$ and $U_{1,2}$ over $\mathbb{F}_2$.

We see that the interval between $0$ and $\langle100\rangle$ and the interval between $\langle010,001\rangle$ and $E$ are coloured as $U_{1,1}$, showing $M|_{E_1}=M/E_2=M_1$. On the other hand, the interval between $0$ and $\langle010,001\rangle$ and the interval between $\langle100\rangle$ and $E$ are coloured as $U_{1,2}$, showing that $M|_{E_2}=M/E_1=M_2$. There is now only one way to colour the rest of the lattice:

Unfortunately, this construction becomes not unique already in dimension 4. If we try to make the direct sum $U_{1,2}\oplus U_{1,2}$, semimodularity of the rank function gives that all 1-dimensional spaces have rank 1 and all 3-dimensional spaces have rank 2. Any 2-dimensional space intersecting $E_1$ or $E_2$ is a basis. But there are 2-dimensional spaces that intersect neither $E_1$ nor $E_2$ (over $\mathbb{F}_2$, there are three of them) and those can be either a basis or a circuit. Any choice will produce another q-matroid.

The solution to this problem is to write the direct sum in a very convoluted way that is not helpful for matroids over sets, but that does have a nice q-analogue. This is the following. As mentioned, let $E=E_1\oplus E_2$. Make a matroid $M_1’$ by adding loops to $M_1$ until its groud space is $E$: $M_1’$ is the q-matroid on $E$ such that $M_1’|_{E_1}=M_1$ and $M_1’|_{E_2}$ consists of only loops. Similarly, let $M_2’$ be the q-matroid on $E$ such that $M_2’|_{E_2}=M_2$ and $M_2’|_{E_1}$ consists of only loops. Now the direct sum $M_1\oplus M_2$ is defined as the matroid union $M_1’\vee M_2’$.

It turns out that adding loops is, inductively, possible in the q-analogue. Also matroid union (as an honour to the name of this blog, surely!) has a well-defined q-analogue: this operation is defined for matroids on the same ground set, and can thus be generalised to q-matroids with the same ground space without the troubles that come with the direct sum of vector spaces. The rank function of the direct sum of two q-matroids is \[ r_{M_1\oplus M_2}(A)=\min_{X\subseteq A}\{r_{M_1′}(X)+r_{M_2′}(X)+\dim A-\dim X\}. \]

An equivalent way to phrase this definition of the direct sum of q-matroids, is by requiring the direct sum to to be the “most independent” q-matroid satisfying $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$. This can be made precise in category theory language.

It is unclear what the independent spaces of the direct sum of two q-matroids are. The vector space sum of an independent space in $M_1$ and an independent space in $M_2$ is independent in the direct sum. But there are many more independent spaces. Many other properties of the direct sum of matroids fail to have a nice q-analogue. What does work in the q-analogue, is that the cyclic flats of the direct sum are exactly the sums of the cyclic flats of $M_1$ and $M_2$.

You might have guessed that if $M_1$ and $M_2$ are q-matroids represented by matrices $G_1$ and $G_2$ (I’m going to use this notion without a formal definition), then their direct sum is not necessarily represented by the matrix \[ \left[ \begin{array}{cc} G_1 & 0 \\ 0 & G_2 \end{array} \right]. \] Interestingly, the question about representability can be translated to the language of linear sets in finite geometry, making it possible to use several results in finite geometry for q-matroids.

References

[AJNZ26] Gianira Alfarano, Relinde Jurrius, Alessandro Neri and Ferdinando Zullo. Representability of the direct sum of uniform q-matroids. Combinatorial Theory, 6 (2026).

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

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

[GLJ24] Heide Gluesing-Luerssen and Benjamin Jany. Decomposition of q-matroids using cyclic flats. SIAM Journal on Discrete Mathematics 38, pp 2940–2970 (2024).

[GLJ25] Heide Gluesing-Luerssen and Benjamin Jany. Representability of the direct sum of q-matroids. Journal of Algebraic Combinatorics 61, 51 (2025).

Presentations of avoiding transversal (q-)matroids

Posted on by
Reply

This post is based on joint work with Gianira N. Alfarano.

Last June, Mark Saaltink wrote on this blog about the q-analogue of transversal matroids. Key to this definition is the rather ingenious idea to not consider transversals, but avoiding transversals. This post explores this idea further. Our goal is to sketch a proof for Saaltink’s conjecture that every (avoiding) transversal q-matroid has a unique minimal presentation. However, we will ignore the q-analogue most of the time, because the setting is also valid for plain old transversal matroids. We describe what appears to be a new algorithm to find maximal / minimal presentations.

Cyclic sets and flats

Before we consider transversals, a quick recap of flats and cyclic sets. Consider a matroid with ground set $E$. The closure operator $\mathop{cl} : 2^E \to 2^E$ is defined by
\[ \mathop{cl}(X) = \{e \in E : r(X \cup e) = r(X)\}, \]
and the cyclic operator $\mathop{cyc} : 2^E \to 2^E$ is defined by
\[ \mathop{cyc}(X) = \{e \in X : r(X \setminus{e}) = r(X)\}.\]
For every $X\in 2^E$, we say that $\mathop{cl}(X)$ is the closure of $X$ and $\mathop{cyc}(X)$ is the cyclic core of $X$. A subset $X \subseteq E$ is a flat if $\mathop{cl}(X) = X$ and a cyclic set if $\mathop{cyc}(X) = X$. Therefore, $X$ is a cyclic flat if for all $y \in E\setminus X$ and $x \in X$,
\[ r(X \cup y) > r(X) \quad \text{and} \quad r(X \setminus {x}) = r(X). \]

Both the closure and the cyclic core are uniquely defined. To find the closure of a set, simply keep adding elements until adding any other element will increase the rank. For the cyclic closure, take away elements such that the rank decreases until there are only elements left that, when deleted, will not change the rank.

It is well known that closure and cyclic core are dual operations: the complement of the closure of a set is the cyclic core of the complement of this set in the dual matroid. We mention also the following.

Lemma. For any set $X\subseteq E$, we have that both $\mathop{cyc}(\mathop{cl}(X))$ and $\mathop{cl}(\mathop{cyc}(X))$ are cyclic flats. In particular, both the cyclic core of a flat and the closure of a cyclic set are cyclic flats.

Avoiding transversals

The definition of an avoiding transversal is due to Saaltink [Saa2025].

Definition. Given an indexed family $\mathcal{X}=(X_1,\ldots,X_k)$ of subsets of some given set $E$, an avoiding transversal of $ \mathcal{X}$ is a set of elements $x_1,x_2,\ldots,x_k$ of $E$, all distinct, with each $x_i\notin X_i$. A partial avoiding transversal of $\mathcal{X}$ is an avoiding transversal of some subfamily of $\mathcal{X}$.

We can make a matroid out of every avoiding transversal.

Theorem. Let $\mathcal{X}$ be an avoiding transversal of a finite set $E$. Then the set of avoiding transversals of $\mathcal{X}$ forms the set of bases of a matroid with ground set $E$.

Let $X_i=E\setminus A_i$. Since every avoiding transversal of $\mathcal{X}=(X_1,\ldots,X_k)$ is a transversal of $\mathcal{A}=(A_1,A_2,\ldots,A_k)$, the class of transversal matroids and the class of avoiding transversal matroids are the same. In the q-analogue, only the class of avoiding transversal q-matroids has a sensible definition. (Saaltink uses the term “transversal q-matroids” for them; we add “avoiding” here to emphasise the link with avoiding transversals and remove confusion.) This is why in the search for more results about q-analogues of transversal matroids, one needs to study avoiding transversals.

Presentations

When the independent sets of a matroid are exactly the partial transversals of $\mathcal{A}=(A_1,A_2,\ldots,A_k)$, we call $\mathcal{A}$ a presentation of $M$. (We will assume that all presentations contain $r(M)=k$ sets.) The representation of a transversal matroid is not necessarily unique, as the next result shows.

Proposition A. Let $\mathcal{A} = (A_1, A_2, \ldots , A_k )$ be a presentation of the transversal matroid $M$ of rank $k$, and let $a\in E\setminus A_1$. Then $\mathcal{A}’ = (A_1\cup \{a\}, A_2, \ldots , A_k )$ is also a presentation of $M$ if and only if $a$ is an isthmus of the restriction $M|(E \setminus A_1)$.

This proposition is due to [BW1971]. If we can add isthmusses to presentations without changing the corresponding matroid, the question arises if a matroid has a maximal presentation, that is, a presentation where adding any element to one of its subsets gives a new matroid. The answer is yes, as was first shown in [Mas1969] and [Bon1972]. Proposition A is a first step in proving this. We will see that the rest of the proof is immediate if we translate Proposition A to avoiding transversals. First, we need a definition.

Definition. Given $A\subseteq E$, we say that a subset $H\subseteq A$ with $|H|=|A|-1$ is a non-spanning $(|A|-1)$-set if it does not contain any basis of $M|A$.

This definition might feel overly complicated and in a sense, it is: a non-spanning $(|E|-1)$-set is the complement of an isthmus. However, with an eye on the q-analogue, we want to avoid isthmusses, because in the q-analogue they do not exist (that is, there can be no 1-dimensional space contained in every basis; see Lemma 5.4 of [JPR2025]). But we can talk about non-spanning $(\dim(E)-1)$-spaces.

We can now translate Proposition A to avoiding transversals.

Proposition B. Let $\mathcal{X} = (X_1, X_2, \ldots , X_k )$ be a presentation of the avoiding transversal matroid $M$ of rank $k$, and let $A\subseteq X_1$ of size $|X_1|-1$. Then $\mathcal{X}’ = (X_1\cap A, X_2, \ldots , X_k )$ is also a presentation of $M$ if and only if $A$ is a non-spanning $(|X_1|-1)$-set of the restriction $M|X_1$.

This point of view now gives us a direct proof of the existence and uniqueness of a minimal presentation of an avoiding transversal matroid: simply take the cyclic core of every set in the presentation! Indeed, intersecting with a non-spanning $(|A|-1)$-set repeatedly produces the cyclic core of a set.

With some extra taking of complements, we can find the maximal representation of a transversal matroid, as we illustrate with an example. It comes from exercise 3 op p.47 of [Oxl2011].

Example. Let $E=\{1,2,3,4,5,6\}$ and $\mathcal{A}=(A_1,A_2,A_3)$ where $A_1=\{1,2,3\}$, $A_2=\{2,3,4\}$ and $A_3=\{4,5,6\}$. The cyclic flats of $M$ are $\emptyset$, $\{5,6\}$, $\{1,2,3\}$ and $E$.

Now $M$ can also be viewed as the avoiding transversal matroid corresponding to $\mathcal{X}=(\{4,5,6\},\{1,5,6\},\{1,2,3\})$. Taking the cyclic core of these subsets gives that $\mathcal{X}’=(\{5,6\},\{5,6\},\{1,2,3\})$ is a minimal presentation of $M$ as an avoiding transversal matroid. Hence, $\mathcal{A}’=(\{1,2,3,4\},\{1,2,3,4\},\{4,5,6\})$ is a maximal presentation of $M$ as a transversal matroid.

This leads us to the question: is this a known procedure to obtain a maximal presentation? Classic texts like [Bru1987] and [BKdM2011] do not mention the cyclic core, but use a much more involved procedure that requires knowing not only the cyclic flats, but also their ranks, and calculating a function that gives the multiplicity of these cyclic flats in the maximal presentation. It feels like the procedure as in the Example is much shorter. Please let us know if we are re-inventing the wheel! We admit to having read only a fraction of the literature on transversal matroids.

Finally, we can now prove Saaltink’s conjecture, because we have exactly the same results for avoiding transversal q-matroids. We can first prove Proposition B by taking a lot of complements in the proof of Proposition A. This is a non-trivial task! But as a result, we get a proof that has a straightforward q-analogue. The conjecture then follows by the same reasoning as above.

Theorem. Let $(X_1,X_2,\ldots,X_k)$ be a presentation of the avoiding transversal q-matroid $M$. Then $(\mathop{cyc}(X_1),\mathop{cyc}(X_2),\ldots,\mathop{cyc}(X_k))$ is the unique minimal presentation of $M$.

References

[BKdM2011] J.E. Bonin, J.P.S. Kung and A. de Mier. Characterizations of Transversal and Fundamental Transversal Matroids. Electronic Journal of Combinatorics, 18(1): P106, 2011.

[Bon1972] J.A. Bondy. Presentations of transversal matroids, Journal of the London Mathematical Society, 5(2): 289-292, 1972.

[Bru1987] R.A. Brualdi. Transversal matroids. In: N. White, editor, Combinatorial geometries, pages 72–97, Cambridge University Press, Cambridge, 1987.

[BW1971] J.A. Bondy and D.J.A. Welsh. Some results on transversal matroids and constructions for identically self-dual matroids, Quarterly Journal of Mathematics, 22(3): 435-451, 1971.

[JPR2025] T. Johnsen, R. Pratihar and T. H. Randrianarisoa. The Euler characteristic, q-matroids, and a Möbius function. Journal of Algebra and Its Applications, 2025.

[Mas1969] J. Mason. Representations of independent spaces. PhD dissertation, University of Wisconsin, Madison WI, 1969.

[Oxl2011] J.G. Oxley. Matroid Theory. Oxford University Press, USA, 2011.

[Saa2025] M. Saaltink. A theory of q-transversals. arXiv:2503.12201, 2025.

A $q$-analogue of delta-matroids

Posted on by
Reply

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 q–g-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 q–g-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 q–g-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.

The combinatorial derived matroid

Posted on by
Reply

This post is co-authored by Ragnar Freij-Hollanti.

As has been mentioned on this blog before, an idée fixe of the late Henry Crapo was to naturally define a matroid $\delta M$ whose ground set is the collection $\mathcal{C}(M)$ of circuits (or the collection $\mathcal{C}(M^*)$ of cocircuits) of an underlying matroid $M$. Similar questions have also been asked by Gian-Carlo Rota. We will call such a construction a derived matroid of $M$, partly in analogy with the construction of derived codes in coding theory. Throughout this blogpost, $n$ will denote the size and $k$ will denote the rank of $M$.

The derived matroid could be seen as a combinatorialization of the notion of syzygies and resolutions in commutative algebra, regarding circuits as combinatorial “relations”, which generate a space in which we can again study “relations”, and so on. From this viewpoint, it is natural to try to define a matroid structure on the set of circuits. On the other hand, it seems like a desirable feature that the nullity of $M$ would give, or at least bound, the number of “independent” circuits (i.e. relations) in $M$, or in other words that the number of independent cocircuits would equal (or be bounded by) the nullity of $M^*$, which is the rank of $M$. In this light studying the sequence of repeated derivations of a matroids $M$ would be more natural if $\delta M$ had as its ground set the cocircuits of $M$. Since the cocircuits are in natural bijection with the hyperplanes of $M$, a derived matroid with ground set $\mathcal{C}(M^*)$ would model the hyperplane arrangement described by the point set in the representable case. There are thus good arguments both in favour of grounding the derived matroid on $\mathcal{C}(M)$ and on $\mathcal{C}(M^*)$. In our paper, we choose the first alternative, but the last word has hardly been said in this debate, and of course, one definition can be obtained from the other by dualizing.

Let us first consider the case for represented matroids, and let $G$ be a $k\times n$ matrix of full rank representing $M$ over a field $\mathbb{F}$. Then, every circuit $C\in\mathcal{C}(M)$ is the inclusion-minimal support of a vector $q_C\in\mathbb{F}^n$ such that $G q_C=\mathbf{0}$, and this vector is unique up to scalar multiple. The collection of vectors $\{q_C\}_{C\in\mathcal{C}(M)}$ represent some matroid with ground set $\mathcal{C}(M)$, and we will denote this matroid by $\delta_{OW}(G)$, where the subscript refers to the authors Oxley and Wang, who studied this construction [OW19].

It is not difficult to see that $\delta_{OW}(G)$ has rank $n-k$, because the circuit vectors together generate the null space of the matrix $G$. While this is certainly a desirable feature, it is an unfortunate fact that the construction $\delta_{OW}$ depends on $G$ rather than only on $M$. The geometrically easiest illustration of this feature may be when $M$ is the uniform matroid $U_{3,6}$, represented by a configuration $P$ of six points in general position in the projective plane. Then, the hyperplane arrangement of the $\binom{6}{2}=15$ lines (through pairs of $P$) can be of two different kinds, as shown in the picture below (not all lines are drawn):

Two possibilities for the derived matroid of $U_{3,6}$

Indeed, in addition the five lines intersecting in each point of $P$, it will generically be the case that all other intersections of lines are distinct. However, it is also possible that three of the lines, that do not share a point in $P$, might meet in a point in the projective plane. In this latter case, the cocircuits corresponding to the three lines will be “dependent”; in the former case they will be “independent” in $\delta_{OW}(Q^*)$.

It is fair to say that the dependence between the three lines in the previous example is “accidental”, in that it is not forced by the matroid structure of $U_{3,6}$ itself. If we are to define “the” derived matroid of the matroid $U_{3,6}$ combinatorially, we in particular want the complements of these lines to be independent. Following this line of thought, we consider independence to be the generic state of things, while dependence is forced by constraints coming from the underlying matroid. Our construction of $\delta M$ is thus twofold. First we identify which collections of circuits “have to” be dependent in any “reasonably defined” derived matroid of $M$. After this, we add just enough other dependent sets, to guarantee that $\delta M$ is indeed a matroid, and we do it in such a way as to not introduce unnecessary dependent sets, and in particular not in low rank.

Let us illustrate this procedure with the infamously non-representable Vámos matroid $M$. All sets of three or fewer elements are independent and among the sets of four elements only the five depicted as grey rectangles in the figure are circuits. All sets of five or more elements are dependent.

The Vámos matroid

The ground set of the derived matroid $\delta M$ has 41 elements, the circuits of $M$. If we consider the three planes $abcd$, $adef$ and $bcef$, we intuitively want this to be a dependent set in $\delta M$, because it “looks like” these planes make a “circuit”. To make this mathematically more precise, we can say that this set of circuits is dependent because its size (3) is larger than the nullity in $M$ of the union of all its elements (these six elements have nullity 2 in $M$). That is to say, we want that a set of circuits is dependent in $M$ if it belongs to the family
$$\mathcal{A}_0:=\{A\subseteq\mathcal{C}:|A|>n(\cup_{C\in A}C)\}.$$
It is readily checked that in the previous example of $U_{6,3}$, the three discussed lines are not in this family, because $3\not>3$.

The above family $\mathcal{A}_0$ gives us a precise description of which collections of circuits “have to” be dependent in $\delta M$. Note that this is a combinatorial description: it does not depend on a representation of the matroid. What we want to do now, is make sure that we find all dependent sets of the derived matroid. To see how to get to this, consider the axioms for the collection $\mathcal{D}$ of dependent sets of a matroid.

  1. $\emptyset\notin\mathcal{D}$;
  2. if $D\in\mathcal{D}$ and $D\subseteq D’$ then $D’\in\mathcal{D}$;
  3. if $D_1,D_2\in\mathcal{D}$ and $D_1\cap D_2\notin\mathcal{D}$, then $(D_1\cup D_2)\setminus\{e\}\in\mathcal{D}$ for all $e\in D_1\cap D_2$.

Our collection $\mathcal{A}_0$ satisfies the first two axioms, but in general, it does not satisfy the third. So we want to add extra elements in order to get a collection that does satisfy (D3). There are two ways to do this, as we see from a logical rewriting of the axiom:

  1. If $D_1, D_2\in\mathcal{D}$, then $D_1\cap D_2\in\mathcal{D}$ or $(D_1\cup D_2)\setminus\{e\}\in\mathcal{D}$ for all $e\in D_1\cap D_2$.

This means that for any $A_1,A_2\in\mathcal{A}_0$, we can either decide that $A_1\cap A_2$ is dependent, or that $(A_1\cup A_2)\setminus{C}$ is dependent for all $C\in A_1\cap A_2$ (or both). If we decide on the first, we will get a lot of small dependent sets, and often this leads to a derived matroid of rank 0. We therefore decide to define the following operations.

Definition. Let $\mathcal{C}$ be the set of circuits of some matroid, and let $\mathcal{A}\subseteq \mathcal{C}$. Then we define the collections
$$\epsilon(\mathcal{A})=\mathcal{A}\cup\left\{(A_1 \cup A_2) \setminus {C} : A_1, A_2\in \mathcal{A}, A_1\cap A_2\not\in\mathcal{A}, C\in A_1\cap A_2\right\}$$ and $${\uparrow}\mathcal{A}=\{A\subseteq \mathcal{C}: \exists A’\in\mathcal{A}: A’\subseteq A\}.$$

Observe that, by definition, $\mathcal{A}\subseteq {{\uparrow} \mathcal{A}}$ and $\mathcal{A}\subseteq \epsilon(\mathcal{A})$ for every $\mathcal{A}\subseteq2^\mathcal{C}$. The operations ${\uparrow}$ and $\epsilon$ are designed to guarantee properties (D2) and (D3) in the matroid axioms.

Definition. Let $M$ be a matroid, and $\mathcal{C}=\mathcal{C}(M)$ its collection of circuits. Define the collection
$$ \mathcal{A}_0:=\{A \subseteq \mathcal{C}: |A|> n(\cup_{C\in A} C)\}. $$
Inductively, we let $\mathcal{A}_{i+1}={\uparrow}\epsilon(\mathcal{A}_i)$ for $i\geq 1$, and
$$\mathcal{A}=\bigcup_{i\geq 0} \mathcal{A}_i.$$

Note that the sequence $\mathcal{A}_i$ is both increasing and contained in the finite set $2^\mathcal{C}$. Hence, we have that $\mathcal{A}_0\subseteq\mathcal{A}$ and $\mathcal{A}=\mathcal{A}_n$ for some $n\geq 0$.

Definition (combinatorial derived matroid). Let $M$ be a matroid with circuits $\mathcal{C}$. Then the combinatorial derived matroid $\delta M$ is a matroid with ground set $\mathcal{C}(M)$ and dependent sets $\mathcal{A}$.

By carefully checking the dependent axioms, we can prove that this definition gives indeed a matroid. In fact, we can prove two more ways to construct this derived matroid, by means of its circuits: we refer the interested reader to the full paper [FJK23].

Theorem. For any matroid $M=(E,\mathcal{C})$ the collection $\mathcal{A}$ is the collection of dependent sets of some matroid with ground set $\mathcal{C}$.

This is good news! We now have a definition of a derived matroid that is purely combinatorial: it does not depend on a representation, and hence it exists for any matroid. As far as we know, this is the first definition of this kind. We also managed to show that there is more good news: this definition behaves well with connectedness. That is, the derived matroid of a direct sum is the direct sum of the derived matroids of the connected components.

Unfortunately, it is not all good news. It is not difficult to show that the rank of $\delta M$ is bounded by $n-k$, as desired, but equality does not always hold. Computer calculations by Knutsen [Knu23] show that the rank of the derived Vámos matroid is 3, and not 4. However, this news is not as bad as it sounds, since the Vámos matroid was shown to not have an adjoint by Cheung [Che74]. The construction of the adjoint of a matroid is, in some sense, the dual of that of the derived matroid: it has the set of cocircuits of $M$ as its ground set.

Many questions are still open regarding this construction of $\delta M$. Most prominently: how does this construction relate to earlier constructions of the derived matroid? In particularly, that of Oxley and Wang, but also to the adjoint of a matroid. For more questions, we refer to the full paper [FJK23]. We hope this post inspired you to think more about derived matroids!

References

[Che74] Cheung, A.L.C. (1974). Adjoints of a geometry. Canadian Mathematical Bulletin, 17(3), 363-365.
[FJK23] Freij-Hollanti, R. & Jurrius, R.P.M.J. & Kuznetsova, O. (2023). Combinatorial Derived Matroids. Electronic Journal of Combinatorics, 30(2), P2.8.
[Knu23] Knutsen, T.D. (2023). Codes, matroids and derived matroids. Master thesis, UiT Arctic University of Norway.
[OW19] Oxley, J & Wang, S. (2019). Dependencies among dependencies in matroids. Electronic Journal of Combinatorics, 26(3), P3.46.