Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-02-11T07:21:18.646Z Has data issue: false hasContentIssue false
  • English
  • Français

Multi-Path Matroids

Published online by Cambridge University Press:  01 March 2007

JOSEPH E. BONIN  and
OMER GIMÉNEZ
JOSEPH E. BONIN
Affiliation:
Department of Mathematics, The George Washington University, Washington, DC 20052, USA (e-mail: jbonin@gwu.edu)
OMER GIMÉNEZ
Affiliation:
Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034, Barcelona, Spaine (e-mail: omer.gimenez@upc.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 2 , March 2007 , pp. 193 - 217
Copyright
Copyright © Cambridge University Press 2006

References

[1]Björner, A. (1992) The homology and shellability of matroids and geometric lattices. In Matroid Applications (White, N., ed.), Cambridge University Press, pp. 226–283.CrossRefGoogle Scholar
[2]Bonin, J., de Mier, A. and Noy, M. (2003) Lattice path matroids: Enumerative aspects and Tutte polynomials. J. Combin. Theory Ser. A 104 63–94.CrossRefGoogle Scholar
[3]Bonin, J. and de Mier, A. Lattice path matroids: Structural aspects. European J. Combin., to appear.Google Scholar
[4]Brylawski, T. and Oxley, J. G. (1992) The Tutte polynomial and its applications. In Matroid Applications (White, N., ed.), Cambridge University Press, pp. 123–225.CrossRefGoogle Scholar
[5]Colbourn, C. J., Provan, J. S. and Vertigan, D. (1995) The complexity of computing the Tutte polynomial on transversal matroids. Combinatorica 15 1–10.CrossRefGoogle Scholar
[6]Edmonds, J. and Fulkerson, D. R. (1965) Transversals and matroid partition. J. Res. Nat. Bur. Standards Sect. B 69B 147–153.CrossRefGoogle Scholar
[7]Giménez, O. and Noy, M. (2006) On the complexity of computing the Tutte polynomial of bicircular matroids. Combin. Probab. Comput. 15 385–395.CrossRefGoogle Scholar
[8]Jaeger, F., Vertigan, D. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108 35–53.CrossRefGoogle Scholar
[9]Oxley,, J. G. (1992) Matroid Theory, Oxford University Press.Google Scholar
[10]Vertigan, D. (1998) Bicycle dimension and special points of the Tutte polynomial. J. Combin. Theory Ser. B 74 378–396.CrossRefGoogle Scholar
[11]Vertigan, D. and Welsh, D. J. A. (1992) The computational complexity of the Tutte plane: The bipartite case. Combin. Probab. Comput. 1 181–187.CrossRefGoogle Scholar
[12]Welsh, D. J. A. (1993) Complexity: Knots, Colourings and Counting, Cambridge University Press.CrossRefGoogle Scholar