Lattice path matroids: enumerative aspects and Tutte polynomials

Abstract

Fix two lattice paths P and Q from (0,0) to (m,r) that use East and North steps with P never going above Q. We show that the lattice paths that go from (0,0) to (m,r) and that remain in the region bounded by P and Q can be identified with the bases of a particular type of transversal matroid, which we call a lattice path matroid. We consider a variety of enumerative aspects of these matroids and we study three important matroid invariants, namely the Tutte polynomial and, for special types of lattice path matroids, the characteristic polynomial and the beta invariant. In particular, we show that the Tutte polynomial is the generating function for two basic lattice path statistics and we show that certain sequences of lattice path matroids give rise to sequences of Tutte polynomials for which there are relatively simple generating functions. We show that Tutte polynomials of lattice path matroids can be computed in polynomial time. Also, we obtain a new result about lattice paths from an analysis of the beta invariant of certain lattice path matroids.

28 pages, 11 figures

Cited by in corpus (40)

• A Little Statistical Mechanics for the Graph Theorist
• Lattice Path Matroids: Structural Properties
• The Lattice of Cyclic Flats of a Matroid
• Lattice path matroids: the excluded minors
• On the Ehrhart Polynomial of Minimal Matroids
• Multi-Path Matroids
• Valuative invariants for large classes of matroids
• Symmetries of statistics on lattice paths between two boundaries
• Lattice Path Matroids: Negative Correlation and Fast Mixing
• Computing the Tutte Polynomial of Lattice Path Matroids Using Determinantal Circuits
• Generalized Counting Constraint Satisfaction Problems With Determinantal Circuits
• Delta-matroids as subsystems of sequences of Higgs lifts
• Lattice Path Matroid Polytopes
• Positroids and Schubert matroids
• A characterization of positroids, with applications to amalgams and excluded minors
• Facial structures of lattice path matroid polytopes
• P-flag spaces and incidence stratifications
• Polynomial Coefficient Enumeration
• The natural matroid of an integer polymatroid
• $\LE$-diagrams and totally positive bases inside the nonnegative Grassmannian
• Connectivity gaps among matroids with the same enumerative invariants
• Matroid basis graph: Counting Hamiltonian cycles
• Toric $g$-polynomials of hook shape lattice Path Matroid Polytopes and product of simplices
• The number of lattice paths below a cyclically shifting boundary
• A free subalgebra of the algebra of matroids
• Matroid base polytope decomposition
• Bergman Complexes of Lattice Path Matroids
• Schubert matroids, Delannoy paths, and Speyer's invariant
• Simple formulas for lattice paths avoiding certain periodic staircase boundaries
• Eulerian-Catalan Numbers
• Some inequalities for the Tutte polynomial
• Well-quasi-ordering in lattice path matroids
• The Young matroid: A multiset extension of the Catalan matroid to arbitrary Young diagrams
• A natural family of flag matroids
• $M$-Shellability of Discrete Polymatroids
• Toric Ideals of Lattice Path Matroids and Polymatroids
• Positroids have the Rayleigh property
• The excluded minors for the intersection of bicircular and lattice path matroids
• A unique factorization theorem for matroids
• On lattice path matroid polytopes: integer points and Ehrhart polynomial