Lattice path matroids

2026-07-09 Improve this page

#Lattice path matroids

The family of lattice path matroids was introduced by J. Bonin, A. de Mier, and M. Noy [BMN03]. This family is closed under all matroid minors (deletions and contractions) and also under matroid duality. All lattice path matroids are transversal matroids. They are also positroids, see [Oh11].

Y. Chen, Y. Li, and M. Yao study the $(a,b)$-Catalan subfamily through valuative invariants [CLY25]. They express the indicator function of an $(a,b)$-Catalan matroid polytope as a weighted sum of indicator functions of direct sums of uniform matroids. This gives explicit formulas for valuative invariants, including Ehrhart positivity and Kazhdan–Lusztig invariants for these Catalan matroids.

The Tutte polynomial for a lattice path matroid can be computed efficiently, see [BMN03]. Moreover, there is a nice combinatorial description of the internal and external activity for the bases.

Example

A skew Ferrers shape and labeling of the East steps.

For a broader introduction to transversal matroids, see the lecture notes by J. Bonin [Bon10].

Example (Lattice path matroid from a Dyck path).

Consider the interval family \[A_1 = \{1,2,3,4,5,6\},\qquad A_2 = \{3,4,5,6,7,8\},\qquad A_3 = \{5,6,7,8,9,10\},\qquad A_4 = \{6,7,8,9,10,11\},\qquad A_5 = \{10,11,12\}.\] The corresponding skew shape is the Young diagram $\lambda/\mu$ with $\lambda = (7,7,7,7,6),\qquad \mu = (5,2,2,1).$ Numbering the skew boxes by the elements of $A_5,\dotsc,A_1$ gives

The skew Ferrers shape and labeling of the North steps.

The upper boundary has North-step set $\{1,3,5,6,10\}$ and East-step set $\{2,4,7,8,9,11,12\}.$

The corresponding naturally labeled width-two permutation poset has chains \[C_N = \{1 \lt 3 \lt 5 \lt 6 \lt 10\},\qquad C_E = \{2 \lt 4 \lt 7 \lt 8 \lt 9 \lt 11 \lt 12\},\] together with the cover relations $2\lt 3,$ $4 \lt 5,$ $9 \lt 10,$ and $1 \lt 12.$

The width-two poset associated with the lattice path matroid example.

The permutation $\pi = [2,4,7,8,9,11,1,12,3,5,6,10]$ defines a permutation poset, and all linear extensions of the width-two poset above are precisely the permutations below $\pi$ in the weak order. Note that $\pi$ is 321-avoiding. Thus, for an ordinary Ferrers shape, the determinant in the LGV section on lattice paths in skew shapes computes the number of linear extensions of the associated width-two permutation poset.

We can also model set systems using a Dyck path. Each set in the set system corresponds to a peak. The peaks are marked with the corresponding set and the shaded boxes are those below and to the right of each peak.

$ A_5 $ $ 12$ $ A_4 $ $ 11$ $ A_3 $ $ 10$ $ 9$ $ A_2 $ $ 8$ $ 7$ $ A_1 $ $ 6$ $ 5$ $ 4$ $ 3$ $ 2$ $ 1$

A basis of the lattice path matroid is then a selection of squares on the diagonal, $d_1,d_2,\dotsc,d_k,$ such that peak $i$ can see the square $d_i.$ Here, $k$ is the number of peaks.

In this model, the rank of the lattice path matroid is the number of peaks of the Dyck path, and the dimension of its base polytope is the number of nonzero entries in the area sequence. Area sequences of the form $[0,1,2,\dotsc,k,k,\dotsc,k]$ correspond to uniform matroids. A combinatorial formula for the $h^*$-vector is provided in [Kim20]; see also [Li12].

The corresponding determinant formula for the lattice-path-matroid basis generating function is given in the LGV section on lattice paths in skew shapes.

#Rook matroids

Rook matroids, introduced in [AJ24], give another matroidal structure on the same skew Ferrers shapes. They form a family of transversal matroids that is compatible with duality, but whose behavior under minors is subtler than for lattice path matroids. They also have the same Tutte polynomial as the corresponding lattice path matroid.

Let $\lambda/\mu$ be a skew Ferrers board with $r$ rows and $c$ columns. Label the rows by $1,\dotsc,r$ from top to bottom, and label the columns by $r+1,\dotsc,r+c$ from left to right. A rook placement is non-attacking if no two rooks share a row or a column. Two rooks form a nesting if one lies strictly southeast of the other. A non-nesting rook placement is a non-attacking placement with no nesting. Let \[\mathrm{NN}_{\lambda/\mu}\] denote the set of non-nesting rook placements on $\lambda/\mu.$ The corresponding non-nesting rook polynomial is \[M_{\lambda/\mu}(t) \coloneqq \sum_k r_k(\lambda/\mu)t^k,\] where $r_k(\lambda/\mu)$ is the number of non-nesting rook placements with $k$ rooks.

For a placement $\rho \in \mathrm{NN}_{\lambda/\mu},$ let $R(\rho)$ be the set of unoccupied row labels and let $C(\rho)$ be the set of occupied column labels. The rook matroid of $\lambda/\mu$ has bases \[\mathcal{R}_{\lambda/\mu} = \{ R(\rho) \cup C(\rho) : \rho \in \mathrm{NN}_{\lambda/\mu} \}.\] Every such set has size $r.$

Theorem (Alexandersson–Jal, [AJ24]).

For every skew shape $\lambda/\mu,$ the collection $\mathcal{R}_{\lambda/\mu}$ is the set of bases of a transversal matroid.

Example

For the skew shape $\lambda/\mu = (4,3,2)/(1),$ the rows are labeled $1,2,3$ and the columns are labeled $4,5,6,7.$ The placement below is non-nesting:

$ 4 $ $ 5 $ $ 6 $ $ 7$ $ 1 $ $ \bullet$ $ 2 $ $ 3 $ $ \bullet $

Here row $2$ is unoccupied and columns $4$ and $7$ are occupied, so this placement gives the basis $R(\rho)\cup C(\rho) = \{2,4,7\}.$

Example

With the row-labeling convention above, the rook matroid of a $k\times(n-k)$ rectangle is the uniform matroid $U_{k,n}.$ Equivalently, an $(n-k)\times k$ rectangle gives $U_{n-k,n}.$

Theorem (Alexandersson–Jal, [AJ24]).

Rook matroids are closed under direct sums and under matroid duality. More precisely, \[\mathcal{R}_{\lambda/\mu}^{*}\cong \mathcal{R}_{\lambda'/\mu'}.\] However, the class of rook matroids is not closed under all minors.

Theorem (Alexandersson–Jal, [AJ24]).

Every rook matroid is a positroid.

Thus both lattice path matroids and rook matroids belong to the class of positroids, even though the two matroid structures on a skew shape are not always isomorphic.

#Relation with lattice path matroids

Write $\mathcal{P}_{\lambda/\mu}$ for the lattice path matroid whose upper and lower boundary paths bound the skew shape $\lambda/\mu.$ There is always a bijection between lattice paths in $\lambda/\mu$ and non-nesting rook placements in $\lambda/\mu:$ place a rook in each valley of the path that lies strictly inside the shape. The bijection is not always a matroid isomorphism.

Theorem (Alexandersson–Jal, [AJ24]).

The rook matroid $\mathcal{R}_{\lambda/\mu}$ is isomorphic to the lattice path matroid $\mathcal{P}_{\lambda/\mu}$ if and only if the skew shape $\lambda/\mu$ avoids the subshape $332/1.$

Equivalently, the obstruction is the matroid $Q_6:$ one has $\mathcal{R}_{332/1}\cong Q_6,$ and $Q_6$ is an excluded minor for lattice path matroids [Bon10]. Thus the rook and lattice-path structures agree for many shapes, but not for all skew shapes.

Under the skew-shape–poset correspondence described below, the same condition can be read as avoidance of an induced cycle poset. Namely, the associated width-two poset has no induced subposet on two three-element chains \[a_1 \lt a_2 \lt a_3,\qquad b_1 \lt b_2 \lt b_3\] whose only cross-chain cover relations are \[a_1 \lt b_3,\qquad b_1 \lt a_3.\] Equivalently, the forbidden induced poset is the subdivision of the four-element crown $C_2$ obtained by inserting one element on two opposite covers. The two crossing cover relations correspond to the outer and inner corners of the $332/1$ subshape.

In the other direction, every lattice path matroid is obtained as a deletion of a sufficiently enlarged rook matroid. If $\lambda$ has $r$ rows, define \[\lambda^\ast = (\lambda_1+r,\lambda_2+r-1,\dotsc,\lambda_r+1),\] and similarly add the staircase $(r-1,r-2,\dotsc)$ to $\mu$ to obtain $\mu^\ast.$ Then \[\mathcal{P}_{\lambda/\mu} \cong \mathcal{R}_{\lambda^\ast/\mu^\ast}\setminus [r].\]

Even when the two matroids are not isomorphic, their Tutte polynomials agree: \[T(\mathcal{R}_{\lambda/\mu};x,y) = T(\mathcal{P}_{\lambda/\mu};x,y).\]

#Base polytopes and valuative invariants

For any matroid $M,$ the matroid base polytope is the convex hull of the indicator vectors of its bases. Thus the rook matroid base polytope is \[\operatorname{conv} \{ \mathbf{e}_{R(\rho)\cup C(\rho)} : \rho\in \mathrm{NN}_{\lambda/\mu} \}.\] The base polytopes of lattice path matroids have an alcoved description and snake decompositions, see [BKV23].

The rook polytope also has a description in row-column coordinates. Besides the inequalities $0\leq x_i,y_j\leq 1$ and the rank equation \[x_1+\dotsb+x_r+y_1+\dotsb+y_c = r,\] the nontrivial inequalities are indexed by the inner and outer corners of the skew shape. If the first $i$ rows occupy the consecutive columns $a_i,\dotsc,b_i,$ an inner corner gives an inequality of the form \[(x_1+\dotsb+x_i) + (y_{a_i}+\dotsb+y_{b_i}) \leq b_i-a_i+1.\] Similarly, if rows $j,j+1,\dotsc,r$ occupy the consecutive columns $a'_j,\dotsc,b'_j,$ an outer corner gives \[(x_j+\dotsb+x_r) + (y_{a'_j}+\dotsb+y_{b'_j}) \leq b'_j-a'_j+1.\]

Bonin and de Mier proved a stronger relation between the two matroids: $\mathcal{P}_{\lambda/\mu}$ and $\mathcal{R}_{\lambda/\mu}$ have the same configuration [BM26]. Consequently they have the same Derksen–Fink $\mathcal{G}$-invariant, and every valuative matroid invariant takes the same value on them. This implies, in particular, that the Tutte polynomials agree and that the Ehrhart polynomials of the two matroid base polytopes agree, even when the matroids are not isomorphic.

The base polytopes of lattice path matroids have positive Ehrhart coefficients, see [FMP26].

D. M. Chen, M. Sanchez, J. Veliz, and Z. Ying introduce lattice path delta-matroids, a delta-matroid analogue of the lattice path construction [CSVY23].

#Rook polynomials and width-two posets

The basis-generating polynomial of a rook matroid is Lorentzian. Consequently, the coefficient sequence of $M_{\lambda/\mu}(t)$ is ultra-log-concave with no internal zeros [BH20, AJ24]. Real-rootedness can still fail. For the square-case shapes attached to generalized snake posets, however, B. Braun and A. Jal prove real-rootedness and an interlacing recurrence [BJ26]; equivalently, these order polytopes have real-rooted $h^*$-polynomials.

The same paper gives a stability application: there is a generalized Catalan matroid, hence a lattice path matroid, whose basis-generating polynomial is not stable. Equivalently, this lattice path matroid does not have the half-plane property, answering a natural question about stability for this family of transversal matroids [COSW04, CW06].

The poset here is the same naturally labeled width-two poset associated with the lattice paths above. Under the bijection between lattice paths and non-nesting rook placements, the rook placements correspond to linear extensions of this poset $P,$ and \[M_{\lambda/\mu}(t) = W_P(t),\] where $W_P(t)$ is the $P$-Eulerian polynomial. This refines the width-two poset example above and is compatible with the weak order description for ordinary Ferrers shapes.

Bibliography

[AJ24]Per Alexandersson and Aryaman Jal. Rook matroids and log-concavity of ${P}$-Eulerian polynomials. arXiv:2410.00127, 2024.

.bib

@article{AlexanderssonJal2024x,
Author = {Per Alexandersson and Aryaman Jal},
Title = {Rook matroids and log-concavity of ${P}$-{E}ulerian polynomials},
Year = {2024},
Eprint = {2410.00127},
  url = {https://arxiv.org/abs/2410.00127},
journal = {arXiv e-prints}
}

[BKV23]Carolina Benedetti, Kolja Knauer and Jerónimo Valencia-Porras. On lattice path matroid polytopes: Alcoved triangulations and snake decompositions. arXiv:2303.10458, 2023.

.bib

@article{BenedettiKnauerValencia2023x,
Author = {Carolina Benedetti and Kolja Knauer and Jerónimo Valencia-Porras},
Title = {On lattice path matroid polytopes: alcoved triangulations and snake decompositions},
Year = {2023},
Eprint = {2303.10458},
  url = {https://arxiv.org/abs/2303.10458},
journal = {arXiv e-prints}
}

[Bon10]Joseph E. Bonin. Lattice path matroids: The excluded minors. Journal of Combinatorial Theory, Series B, 100(6):585–599, November 2010.

.bib

@article{Bonin2010,
  title = {Lattice path matroids: {T}he excluded minors},
  volume = {100},
  ISSN = {0095-8956},
  url2 = {http://dx.doi.org/10.1016/j.jctb.2010.05.001},
  DOI = {10.1016/j.jctb.2010.05.001},
  number = {6},
  journal = {Journal of Combinatorial Theory,  Series B},
  publisher = {Elsevier BV},
  author = {Bonin,  Joseph E.},
  year = {2010},
  month = nov,
  pages = {585–599}
}

[Bon10]Joseph E. Bonin. An introduction to transversal matroids. 2010. Lecture notes

.bib

@misc{Bonin2010TransversalNotes,
  author = {Bonin, Joseph E.},
  title = {An introduction to transversal matroids},
  year = {2010},
  note = {Lecture notes}
}

[BM26]Joseph E. Bonin and Anna Mier. A construction that preserves the configuration of a matroid, with applications to lattice path matroids. The Electronic Journal of Combinatorics, 33(1):#P1.11, 2026.

.bib

@article{BoninMier2026,
  author = {Bonin, Joseph E. and {de Mier}, Anna},
  title = {A construction that preserves the configuration of a matroid, with applications to lattice path matroids},
  journal = {The Electronic Journal of Combinatorics},
  volume = {33},
  number = {1},
  pages = {\#P1.11},
  year = {2026},
  doi = {10.37236/14238},
  url = {https://doi.org/10.37236/14238}
}

[BMN03]Joseph Bonin, Anna Mier and Marc Noy. Lattice path matroids: Enumerative aspects and Tutte polynomials. Journal of Combinatorial Theory, Series A, 104(1):63–94, October 2003.

.bib

@article{BoninMierNoy2003,
  title = {Lattice path matroids: enumerative aspects and {T}utte polynomials},
  volume = {104},
  ISSN = {0097-3165},
  url = {http://dx.doi.org/10.1016/S0097-3165(03)00122-5},
  DOI = {10.1016/s0097-3165(03)00122-5},
  number = {1},
  journal = {Journal of Combinatorial Theory,  Series A},
  publisher = {Elsevier BV},
  author = {Bonin,  Joseph and de Mier,  Anna and Noy,  Marc},
  year = {2003},
  month = oct,
  pages = {63--94}
}

[BH20]Petter Brändén and June Huh. Lorentzian polynomials. Annals of Mathematics, 192(3), November 2020.

.bib

@article{BrandenHuh2020,
  title = {Lorentzian polynomials},
  volume = {192},
  ISSN = {0003-486X},
  url = {http://dx.doi.org/10.4007/annals.2020.192.3.4},
  DOI = {10.4007/annals.2020.192.3.4},
  number = {3},
  journal = {Annals of Mathematics},
  publisher = {Annals of Mathematics},
  author = {Br{\"{a}}nd{\'{e}}n,  Petter and Huh,  June},
  year = {2020},
  month = nov
}

[BJ26]Benjamin Braun and Aryaman Jal. Order polytopes of generalized snake posets are $h^*$-real-rooted. arXiv:2607.00922, 2026.

.bib

@article{BraunJal2026x,
  author = {Benjamin Braun and Aryaman Jal},
  title = {Order polytopes of generalized snake posets are {$h^*$}-real-rooted},
  year = {2026},
  eprint = {2607.00922},
  url = {https://arxiv.org/abs/2607.00922},
  journal = {arXiv e-prints}
}

[CLY25]Yiming Chen, Yao Li and Ming Yao. Valuative invariants of Catalan matroids. arXiv:2503.19621, 2025.

.bib

@article{ChenLiYao2025x,
  author = {Yiming Chen and Yao Li and Ming Yao},
  title = {Valuative Invariants of {C}atalan Matroids},
  year = {2025},
  eprint = {2503.19621},
  url = {https://arxiv.org/abs/2503.19621},
  journal = {arXiv e-prints}
}

[CSVY23]Douglas M. Chen, Mario Sanchez, John Veliz and Zhiyan Ying. Lattice Path Delta Matroids. arXiv:2311.15441, 2023.

.bib

@article{ChenSanchezVelizYing2023x,
  author = {Douglas M. Chen and Mario Sanchez and John Veliz and Zhiyan Ying},
  title = {Lattice {P}ath {D}elta {M}atroids},
  year = {2023},
  eprint = {2311.15441},
  url = {https://arxiv.org/abs/2311.15441},
  journal = {arXiv e-prints}
}

[COSW04]Young-Bin Choe, James G. Oxley, Alan D. Sokal and David G. Wagner. Homogeneous multivariate polynomials with the half-plane property. Advances in Applied Mathematics, 32(1-2):88–187, January 2004.

.bib

@article{ChoeOxleySokalWagner2004,
  doi = {10.1016/s0196-8858(03)00078-2},
  url2 = {https://doi.org/10.1016/s0196-8858(03)00078-2},
  year = {2004},
  month = jan,
  publisher = {Elsevier {BV}},
  volume = {32},
  number = {1-2},
  pages = {88--187},
  author = {Young-Bin Choe and James G. Oxley and Alan D. Sokal and David G. Wagner},
  title = {Homogeneous multivariate polynomials with the half-plane property},
  journal = {Advances in Applied Mathematics}
}

[CW06]Youngbin Choe and David G. Wagner. Rayleigh matroids. Combin. Probab. Comput., 15(5):765–781, 2006.

.bib

@article {ChoeWagner2006,
    AUTHOR = {Choe, Youngbin and Wagner, David G.},
     TITLE = {Rayleigh matroids},
   JOURNAL = {Combin. Probab. Comput.},
  FJOURNAL = {Combinatorics, Probability and Computing},
    VOLUME = {15},
      YEAR = {2006},
    NUMBER = {5},
     PAGES = {765--781},
      ISSN = {0963-5483,1469-2163},
   MRCLASS = {05B35},
  MRNUMBER = {2248326},
MRREVIEWER = {Carles\ Padr\'{o}},
       DOI = {10.1017/S0963548306007541},
       URL = {https://doi.org/10.1017/S0963548306007541},
}

[FMP26]Luis Ferroni, Alejandro H. Morales and Greta Panova. Ehrhart positivity for lattice path matroids. arXiv:2605.22673, 2026.

.bib

@article{FerroniMoralesPanova2026x,
  author = {Luis Ferroni and Alejandro H. Morales and Greta Panova},
  title = {Ehrhart positivity for lattice path matroids},
  year = {2026},
  eprint = {2605.22673},
  url = {https://arxiv.org/abs/2605.22673},
  journal = {arXiv e-prints}
}

[Kim20]Donghyun Kim. A combinatorial formula for the Ehrhart h*-vector of the hypersimplex. Journal of Combinatorial Theory, Series A, 173:105213, 2020.

.bib

@article{Kim2020,
  author = {Kim, Donghyun},
  title = {A combinatorial formula for the {E}hrhart h*-vector of the hypersimplex},
  year = {2020},
  journal = {Journal of Combinatorial Theory, Series A},
  volume = {173},
  pages = {105213},
  publisher = {Elsevier BV},
  doi = {10.1016/j.jcta.2020.105213},
  url = {http://dx.doi.org/10.1016/j.jcta.2020.105213},
  issn = {0097-3165}
}

[Li12]Nan Li. Ehrhart $h^*$-vectors of hypersimplices. Discrete & Computational Geometry, 48(4):847–878, 2012.

.bib

@article{Li2012,
  author = {Nan Li},
  title = {Ehrhart {$h^*$}-vectors of hypersimplices},
  year = {2012},
  journal = {Discrete \& Computational Geometry},
  volume = {48},
  number = {4},
  pages = {847--878},
  doi = {10.1007/s00454-012-9452-2},
  url = {https://doi.org/10.1007/s00454-012-9452-2}
}

[Oh11]Suho Oh. Positroids and Schubert matroids. Journal of Combinatorial Theory. Series A, 118(8):2426–2435, 2011.

.bib

@article{Oh2011,
  author = {Suho Oh},
  title = {Positroids and {S}chubert matroids},
  journal = {Journal of Combinatorial Theory. Series A},
  volume = {118},
  number = {8},
  pages = {2426--2435},
  year = {2011},
  doi = {10.1016/j.jcta.2011.06.006},
  url = {https://doi.org/10.1016/j.jcta.2011.06.006}
}