From lattice paths to matroids

Lattice paths and Catalan numbers were some of the favourite topics in my recent combinatorics course. And while we didn’t cover them in class, I was reminded of lattice path matroids.

The systematic study of lattice path matroids was initiated by Joe Bonin, Anna de Mier, and Marc Noy. The results I describe here (as well as their proofs) can all be found in this paper by Bonin and De Mier.

A north-east lattice path (I will call them lattice paths for simplicity) is a sequence $v_0 = (0,0), v_1, \ldots, v_\ell$ of points in the lattice $\mathbb{Z}^2$ such that each step $P_i = v_i – v_{i-1}$ is either in the east direction $E = (1,0)$ or in the north direction $N = (0,1)$. As such lattice paths always start at the origin, they are in one-to-one correspondence with words over the alphabet $\{E,N\}$.

There are exactly $\binom{a+b}{b}$ lattice paths to $(a,b)$, as all such paths have $a+b$ steps, and identifying the $b$ north steps among them suffices to describe the path.

Given a lattice path $P$ to $(a,b)$, written as a sequence $P_1P_2\ldots P_{a+b}$ of $a$ east steps and $b$ north steps, we can record the north steps as follows: $$\mathcal{N}(P) = \{i : P_i = N\}.$$

All $b$-element subsets of $[a+b]$ appear as $\mathcal{N}(P)$ for some lattice path $P$ to $(a,b)$; in other words, the set of all $\mathcal{N}(P)$, as $P$ ranges over the lattice paths to $(a,b)$, is the set of bases of the rank-$b$ uniform matroid on $[a+b]$. Lattice path matroids generalise this construction.

Let $P$ and $Q$ be two lattice paths to $(a,b)$. We say that $P \le Q$ if $P$ never goes above $Q$; this defines a partial order on the set of all lattice paths to $(a,b)$. For $P \le Q$, we define the matroid $M[P,Q]$ on $[a,b]$ with set of bases $$\{\mathcal{N}(R) : P \le R \le Q\}.$$

Proposition. $M[P,Q]$ is a matroid.

The matroid $M[P,Q]$ records (the north steps of) all lattice paths between $P$ and $Q$; an arbitrary matroid is called a lattice path matroid if it is isomorphic to $M[P,Q]$ for some $P$ and $Q$. Here are some examples:

• $M[E^aN^b, N^bE^a]$ is the rank-$b$ uniform matroid on $[a+b]$. Here, the first boundary path is the one formed by $a$ east steps followed by $b$ north steps, and the second boundary path is the one formed by $b$ north steps folled by $a$ east steps.
• $M[P,P] \cong U_{b,b} \oplus U_{0,a}$ for any lattice path $P$ to $(a,b)$.
• $M[E^nN^n, (EN)^n]$ is the Catalan matroid with exactly $\frac{1}{n+1}\binom{2n}{n}$ bases.

Properties of $M[P,Q]$ can (in principle) be explained in terms of $P$ and $Q$ alone. We will need the following result later.

Proposition. The element $i$ is a coloop of $M[P,Q]$ if and only if $P_{i-1} = Q_{i-1}$ and $P_i – P_{i-1} = Q_i – Q_{i-1} = N$. The element $i$ is a loop of $M[P,Q]$ if and only if $P_{i-1} = Q_{i-1}$ and $P_i – P_{i-1} = Q_i – Q_{i-1} = E$.

An attractive property of the class of lattice path matroids is that it is closed under duality and minors. Both of these operations have interpretations in terms of lattice paths.

Duality

Let $\mathcal{N}(R)$ be a basis of $M[P,Q]$. Then the complement of $\mathcal{N}(R)$ in $[a+b]$ is a basis of the dual matroid $M[P,Q]^*$: its elements correspond precisely to the east steps in $R$. This inspires the following definition.

For a lattice path $R$, let $R^*$ be the lattice path obtained from $R$ by flipping the roles of north and east steps. If $R$ is a lattice path to $(a,b)$, then $R^*$ is a lattice path to $(b,a)$. Geometrically, $R^*$ is obtained from $R$ by reflecting it in the line $y=x$. It is clear from the geometric perspective that if $P \le R \le Q$, then $Q^* \le R^* \le P^*$, from which it can be shown that the dual of $M[P,Q]$ is again a lattice path matroid.

Proposition. $M[P,Q]^* = M[Q^*, P^*]$.

Minors

Showing that the class of lattice path matroids is minor-closed requires a bit more work. Fortunately, in view of the previous result, it suffices to show that deleting a single element from $M[P,Q]$ results in a new lattice path matroid.

So let $M = M[P,Q]$ be a lattice path matroid and let $i$ be an element of $M$. If $i$ is a loop or coloop of $M$, then $P$ and $Q$ coincide in the $i$-th step; a lattice path representation can be obtained from $P$ and $Q$ by deleting this step from both paths. (When drawing $P$ and $Q$ in $\mathbb{Z}^2$, the resulting disconnected parts of the lattice paths should be connected up again by “sliding” the north-east component one unit to the south (when $i$ is a coloop) or to the west (when $i$ is a loop).)

When $i$ is neither a loop nor a coloop, the bases of $M\backslash i$ are the bases of $M$ that do not contain $i$. In terms of lattice paths, this means that the lattice paths $R$ corresponding to bases of $M\backslash i$ satisfy $P \le R \le Q$ and $R_i – R_{i-1} = E$: we disallow north steps starting from any point $(u,v)$ such that $u+v=i-1$. We obtain lattice paths $P’$ and $Q’$ representing $M\backslash i$ by “merging” the two squares on either side of such north steps. More precisely, we obtain $P’$ from $P$ by deleting the last east step at or before the $i$-th step, and $Q’$ from $Q$ by removing the first east step at or after the $i$-th step. See the figure for an illustrative example.

Proposition. $M[P,Q]\backslash i \cong M[P’,Q’]$.

We conclude that the class of lattice path matroids is closed under taking minors. Joe Bonin identified the excluded minors for the class of lattice path matroids: they comprise the rank-3 wheel and whirl, a rank-3 matroid on seven elements called $R_3$ and its dual, and five infinite families.

The class of lattice paths has many more interesting properties. For example, all of them are transversal matroids and their Tutte polynomials can be computed in polynomial time. I refer to the original papers by Bonin, De Mier, and Noy for this and more.

This is a guest post by Mark Saaltink.

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

$q$-matroids, briefly

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

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

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

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

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

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

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

Normal transversals, abnormally

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

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

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

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

Theorem

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

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

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

$q$-transversals, finally

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

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

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

Theorem

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

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

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

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

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

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

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

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

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

References

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

References:

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

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

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

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

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