Multi-Path Matroids

• DOI: 10.1017/s0963548306007942
• Publication Date: 2006-09-20T14:29:46Z
• Authors: JOSEPH E. BONIN; OMER GIMÉNEZ
• Keywords: Lattice (music); Transversal (combinatorics); Tutte polynomial; Oriented matroid

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