The systematic study of lattice path matroids was initiated by Joe Bonin, Anna de Mier, and Marc Noy<\/a>. The results I describe here (as well as their proofs) can all be found in this paper by Bonin and De Mier<\/a>.<\/p>\n\n\n\n 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\\}$.<\/p>\n\n\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.<\/p>\n\n\n\n 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\\}.$$<\/p>\n\n\n\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.<\/p>\n\n\n\n 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\\}.$$<\/p>\n\n\n\n Proposition.<\/strong> $M[P,Q]$ is a matroid.<\/p>\n\n\n\n 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:<\/p>\n\n\n\n Properties of $M[P,Q]$ can (in principle) be explained in terms of $P$ and $Q$ alone. We will need the following result later.<\/p>\n\n\n\n Proposition.<\/strong> 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$.<\/p>\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n Proposition.<\/strong> $M[P,Q]^* = M[Q^*, P^*]$.<\/p>\n\n\n 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.<\/p>\n\n\n\n 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).)<\/p>\n\n\n\n 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.<\/p>\n\n\n\n Proposition.<\/strong> $M[P,Q]\\backslash i \\cong M[P’,Q’]$.<\/p>\n\n\n We conclude that the class of lattice path matroids is closed under taking minors. Joe Bonin identified the excluded minors<\/a> 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.<\/p>\n\n\n\n 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.<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading ![\"A](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2025\/10\/matroid-union-lattice-paths-path.png\")
<\/a>\n
![\"\"](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2025\/10\/matroid-union-lattice-paths-uniform-catalan-2.png\")
<\/a>![\"Loops](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2025\/10\/matroid-union-lattice-paths-coloop-loop.png\")
<\/a>Duality<\/h2>\n\n\n\n
![\"The](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2025\/10\/matroid-union-lattice-paths-dual.png\")
<\/a>Minors<\/h2>\n\n\n\n
![\"Single-element](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2025\/10\/matroid-union-lattice-paths-minor.png\")
<\/a>