Multi-Path Matroids

Abstract

We introduce the minor-closed, dual-closed class of multi-path matroids. We give a polynomial-time algorithm for computing the Tutte polynomial of a multi-path matroid, we describe their basis activities, and we prove some basic structural properties. Key elements of this work are two complementary perspectives we develop for these matroids: on the one hand, multi-path matroids are transversal matroids that have special types of presentations; on the other hand, the bases of multi-path matroids can be viewed as sets of lattice paths in certain planar diagrams.

24 pages; 10 figures

References in corpus (2)

• Lattice path matroids: enumerative aspects and Tutte polynomials
• Lattice Path Matroids: Structural Properties

Cited by in corpus (9)

• Lattice Path Matroids: Structural Properties
• Lattice path matroids: the excluded minors
• 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
• A characterization of positroids, with applications to amalgams and excluded minors
• Connectivity gaps among matroids with the same enumerative invariants
• On lattice path matroid polytopes: integer points and Ehrhart polynomial
• The excluded minors for the intersection of bicircular and lattice path matroids