Multi-Path Matroids

DOI10.1017/S0963548306007942MaRDI QIDQ5295409zbMATH OpenOpenAlexFDO

Authors Joseph E. Bonin, Omer Giménez

Publication date 30 July 2007

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0410425

zbMATH Keywords

Tutte polynomial

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

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.

Recommendations

• Paths in circuit graphs of matroids
• Paths and cycles in matroid base graphs
• Paths on polymatroids
• Lattice path matroids: structural properties
• scientific article; zbMATH DE number 1028231
• scientific article; zbMATH DE number 922670
• Matroids
• Matroids
• Path decompositions of multigraphs

Cited in

(20)

• Paths on polymatroids
• Chords and disjoint paths in matroids
• The Catalan matroid
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• On lattice path matroid polytopes: integer points and Ehrhart polynomial
• Delta-matroids as subsystems of sequences of Higgs lifts
• The family of bicircular matroids closed under duality
• Facial structures of lattice path matroid polytopes
• Lattice path matroids: structural properties
• A free subalgebra of the algebra of matroids
• Ideal hierarchical secret sharing and lattice path matroids
• Generalized counting constraint satisfaction problems with determinantal circuits
• Computing the Tutte polynomial of lattice path matroids using determinantal circuits
• Lattice path matroids: the excluded minors
• Connectivity gaps among matroids with the same enumerative invariants
• Cyclic Matroids
• The excluded minors for the intersection of bicircular and lattice path matroids
• Lattice path matroids and quotients
• A characterization of positroids, with applications to amalgams and excluded minors
• Hamiltonian connectivity of some base-cobase graphs

This page was built for publication: Multi-Path Matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5295409)