Tag Archives: q-analogue

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 $q$-analogue of a matroid

Posted on by
Reply

The goal of this post is to give you some intuition and background about the q-analogue of a matroid. To keep this a gentle introduction, I’ll leave out most technical details. If you are interested, you can read more in [JP2018] and [BCJ2017].

Before discussing what a q-analogue is, let me start by giving the point of view of matroids that will help us with this. As an example, consider the following matroid.

We will describe the rank function of this matroid via a colouring of the Boolean lattice. The matroid is on four points, so we look at the lattice of all subsets of the set of four elements. We colour all covers in this lattice: we make them red if the rank goes up and green if it stays the same. So our matroid becomes:

For every element in the lattice, we can find its rank by counting the number of red lines in a chain from the bottom to this element. For example, $\{a,c\}$ has rank 2 and $\{b,c\}$ has rank 1. The whole matroid has rank 3: no matter what path we take from $\emptyset$ to $\{a,b,c,d\}$, we always use 3 red lines.

In this way we can represent any matroid on $n$ points as a colouring of the Boolean lattice of height $n$. We can ask ourselves the opposite question as well: suppose I want to colour a Boolean lattice, how do I do that in a way that gives a matroid? We call such a colouring matroidial. It turns out it is enough to look at the intervals of height two, that I will call diamonds. A colouring is matroidial if and only if every diamond is of one of the following types:

(The mixed diamond can of course be mirrored, this depends on how you draw the Boolean lattice.) Note that both paths from the bottom to the top of the diamond have the same number of red edges: we need this for the rank function to be well defined. Also, we cannot have a diamond where the bottom edges are green and the top are red, because this would violate the semimodularity of the rank function. It is equivalent to saying that the sum of two loops can never have rank 1.

If you want to familiarise yourself more with this way of looking at matroids, you can ask yourself how to recognise certain matroid properties in this picture. For example, an independent set is an element of the Boolean lattice such that the whole interval between the bottom (the empty set) and this element only has red lines. The closure of a subset is found by going up from the element via green lines only as far as possible. Can you see how to characterise flats, bases, hyperplanes, and circuits in this picture? Also, some slightly more difficult questions: how would duality work? And taking minors? (You can find the answers to all these questions in the first pages of [BCJ2017].)

Now that we have this image of a matroid in mind, let’s talk about the q-analogue. The concept of a q-analogue in combinatorics started to get attention in the 1980’s. The idea is to ‘generalise’ from a finite set to a finite dimensional vectorspace. This space was originally over a finite field, because then we can count things. I will keep that point of view here, but note that as long as the dimension is finite, the underlying field can be infinite.

Here is a first example of a q-analogue. We know that we can count the number of subsets of size $k$ of a set of size $n$ with the binomial ${n\choose k}$. The q-analogue of this is the Gaussian binomial, that counts the number of $k$-dimensional subspaces of an $n$-dimensional space over $\mathbb{F}_q$. It is given by

\[ \genfrac{[}{]}{0pt}{}{n}{k}_q=\frac{(q^n-1)(q^{n-1}-1)\cdots(q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\cdots(q-1)}. \]

In essence, what you do by taking a q-analogue is going from the Boolean lattice to the subspace lattice, the lattice of a vectorspace and all its subspaces. If you want to go back from the q-analogue to the set-case, you let $q\to1$. One could say that set theory is just geometry over the field of one element. If that sounds intriguing to you, I recommend the very accessible paper [Coh2004] on this topic.

During the last decade, q-analogues became in fashion again because of their application to network coding. Together with Ruud Pellikaan, who had been my PhD supervisor, I started thinking about the q-analogue of a matroid around 2013. (Don’t worry, I’ll tell you what that is in a minute.) Our motivation came from coding theory: in my thesis, I had studied the relation between the weight enumerator of a code and the Tutte polynomial of a matroid, and we wanted to do the same thing for the q-analogue of codes, that are used in network coding. To achieve this we needed the q-analogue of a matroid and its Tutte polynomial. That looked easy enough at first, but the Tutte polynomial for q-matroids is still not well-defined, as far as I know.

A few years later I attended a matroid workshop in Eindhoven, were I was going to speak about q-matroids. Already in the first coffee break I was introduced to Henry Crapo, who had read my abstract and showed great interested in my work. At that time I was a postdoc and you can imagine I was a bit nervous about such a big name showing interest in what I was doing. It turned out that Henry developed already the idea of a q-matroid in his PhD thesis in 1964, but it became somewhat forgotten. His point of view was quite different from mine and did not have anything to do with vectorspaces at all. But our two approaches turned out to complement each other very well and this was the start of a great collaboration. Unfortunately, we did not get the time to finish some of our big questions.

Now, back to the mathematics. The q-analogue of a matroid, that we call a q-matroid, is a colouring of the subspace lattice. Here is an example:

And here is another one:

In both cases, the underlying vectorspace is $\mathbb{F}_2^3$ and the elements of the lattice are give by their Plücker coordinates. We see that the first q-matroid has rank 1, where the second one has rank 2.

Just as with the colouring of the Boolean lattice, we can say when we find such a colouring to be matroidial. We look again at diamonds, the intervals of heigh two. Now there are not 2 elements in the middle of a diamond, but $q+1$ (the number of points on a projective line). The following diamonds are allowed:

The interesting case here is the mixed diamond. It can have only one green line at the bottom. If there were two, the whole diamond has to be green: the sum of two loops can not have rank 1.

We can define a q-matroid also by its rank function. Then it is a pair $(E,r)$ where $E$ is a finite dimensional vectorspace and $r$ an integer valued function defined on the subspaces of $E$. For all subspaces $A$ and $B$ of $E$ the rank function satisfies:

  1. $0\leq r(A)\leq\dim(A)$.
  2. If $A\subseteq B$ then $r(A)\leq r(B)$.
  3. $r(A+B)+r(A\cap B)\leq r(A)+r(B)$.

These axioms are a direct q-analogue of the rank axioms for classical matroids. In the first axiom, cardinality of a set is replaced by dimension of a subspace. Both are the height of the element in the underlying lattice. In the last axiom the union of two subsets is replaced by the direct sum of subspaces: both are the join of elements in the underlying lattice.

Inspired by the above relatively straightforward q-analogues of two cryptomorphic definitions of a matroid, it is a logical thing to ask if we can do this for more cryptomorphisms. Define an independent space of a q-matroid as a subspace whose rank is equal to its dimension. If we denote the family of all independent spaces by $\mathcal{I}$, we could write down the following axioms for independent spaces:

  1. $\mathcal{I}\neq\emptyset$.
  2. If $J\in\mathcal{I}$ and $I\subseteq J$, then $I\in\mathcal{I}$.
  3. If $I,J\in\mathcal{I}$ with $\dim I<\dim J$, then there is some 1-dimensional subspace $x\subseteq J$, $x\not\subseteq I$ with $I+x\in\mathcal{I}$.

But here is an interesting thing: these properties follow from the rank axioms, but they do not completely define a q-matroid! (This object is studied in the work of Terwilliger [Ter1996].) You can check that the following diamond is not excluded by the three independence axioms:

So, we need an extra axiom for independent spaces. This one works:

  1. Let $A,B\subseteq E$ and let $I,J$ be maximal independent subspaces of $A$ and $B$, respectively. Then there is a maximal independent subspace of $A+B$ that is contained in $I+J$.

(If you find this axiom not very appealing, I agree. But it is exactly what goes wrong if you try to prove semimodularity from the independence axioms. It might be that there is a ‘prettier’ way to solve the need for a fourth axiom — maybe by changing the third axiom? I’m open to suggestions!)

Note that the similar statement for the classical case follows from the three standard independence axioms. This is a good example of something that makes q-analogues difficult: if you add two subspaces $A$ and $B$ together, you get not only all 1-dimensional subspaces that were already in $A$ or $B$, but a whole lot more. It can be hard to control what is going on with these extra 1-dimensional spaces.

Another difficulty in q-analogues is the notion of a complement. For sets, if $A$ is a subset of $E$, then the complement of $A$ in $E$ is just the set of all elements that are in $E$ but not in $A$. For spaces, this is a lot more difficult. If $A$ is a subspace of $E$, we could say that we want its complement to contain all 1-dimensional subspaces of $E$ that are not in $A$. But these don’t form a subspace. We could also take the orthogonal complement $A^\perp$ of $A$ in $B$: this is well-defined and it has the dimension we want. But it can be that $A\cap A^\perp$ is nontrivial (remember we are working over finite fields) and this gives problems. Another option is to take a subspace $A^c$ such that $A\oplus A^c=E$, but then $A^c$ is not unique. All these options might be the type of complement you need in a proof of a q-analogue, but it is not always clear which one.

As an illustration, think about the proof that the complements of bases of a matroid form the family of bases of the dual matroid. This involves proving that the (strong) base exchange axiom holds for all complements of bases:

  • If $B_1$ and $B_2$ are bases and $x\in B_1-B_2$, then there is and element $y\in B_2-B_1$ such that $B_1-x\cup y$ and $B_2-y\cup x$ are both bases.

For classical matroids, this all works very smoothly: removing element $x$ and adding element $y$ form a basis is like removing $y$ and adding $x$ to its complement. For q-analogues, this proof is an absolute disaster, no matter which definition of complement you try. So in order to define the dual of a q-matroid, we have to come up with something else that does not use bases. Such as: “Take the coloured lattice, put it upside down, and interchange red and green lines.” I’ll leave it to you to convince yourself that this gives again a q-matroid. (Hint: apply this procedure to the diamonds of a matroidial colouring.)

The theory of q-matroids is still in its early stages of development. There are many, many concepts in matroid theory out there waiting for a q-analogue. Like the Tutte polynomial, as already mentioned. But there are more basic questions to answer first. Take for example the fact that a circuit and a cocircuit can never have one element in common. Is it the case in q-matroids that a circuit and a cocircuit can never intersect in a 1-dimensional subspace? Or, how about a q-analogue of a graph that generalises to a q-matroid? Inspiration for open questions can be found in the last section of [JP2018], or you can simply start q-ifying your own favourite matroid result.

References

[BCJ2017] Bollen, G. & Crapo, H. & Jurrius, R.P.M.J. (2017). The Tutte q-polynomial. Eternal preprint. arXiv

[Coh2004] Cohn, H. (2004). Projective geometry over $\mathbb{F}_1$ and the Gaussian binomial coefficients. American Mathematical Monthly, 111:487–495. pdf

[JP2018] Jurrius, R.P.M.J. & Pellikaan, R. (2018). Defining the q-analogue of a matroid. Electronic Journal of Combinatorics, 25(3), P3.2. doi

[Ter1996] Terwilliger, P. (1996). Quantum matroids. In: Bannai, E. & Munemasa, A., editors, Progress in Algebraic Combinatorics, volume 24 of Advanced Studies in Pure Mathematics. Mathematical Society of Japan, Tokyo, 1996.