Combinatorics, Probability and Computing

Table of Contents - 2007 - Volume 16, Issue 02  

Paper

Multi-Path Matroids

JOSEPH E. BONINa1 and OMER GIMÉNEZa2†

a1 Department of Mathematics, The George Washington University, Washington, DC 20052, USA (e-mail: jbonin@gwu.edu)

a2 Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034, Barcelona, Spaine (e-mail: omer.gimenez@upc.edu)

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.

(Received October 19 2004)

(Revised December 06 2005)

Footnotes

† Partially supported by Beca Fundació Crèdit Andorrà. Current address: Universitat Pompeu Fabra, Departament de Tecnologia, Passeig de Circunval.lació 8, 08003 Barcelona, Spain.