Lattice path matroids: structural properties. (English) Zbl 1087.05014

Summary: This paper studies structural aspects of lattice path matroids. Among the basic topics treated are direct sums, duals, minors, circuits, and connected flats. One of the main results is a characterization of lattice path matroids in terms of fundamental flats, which are special connected flats from which one can recover the paths that define the matroid. We examine some aspects related to key topics in the literature of transversal matroids and we determine the connectivity of lattice path matroids. We also introduce notch matroids, a minor-closed, dual-closed subclass of lattice path matroids, and we find their excluded minors.


05B35 Combinatorial aspects of matroids and geometric lattices
Full Text: DOI arXiv Link


[1] Ardila, F., The Catalan matroid, J. Combin. Theory Ser. A, 104, 49-62 (2003) · Zbl 1031.05030
[2] Bondy, J. A., Presentations of transversal matroids, J. London Math. Soc. (2), 5, 289-292 (1972) · Zbl 0262.05017
[3] Bondy, J. A.; Welsh, D. J.A., Some results on transversal matroids and constructions for identically self-dual matroids, Q. J. Math. Oxford (2), 22, 435-451 (1971) · Zbl 0294.05019
[4] Bonin, J.; Giménez, O., Multi-path matroids, v1 19 October 2004
[5] Bonin, J.; de Mier, A.; Noy, M., Lattice path matroids: enumerative aspects and Tutte polynomials, J. Combin. Theory Ser. A, 104, 63-94 (2003) · Zbl 1031.05031
[6] Brualdi, R. A., Transversal matroids, (White, N., Combinatorial Geometries (1987), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 72-97 · Zbl 0294.05018
[7] Brualdi, R. A.; Dinolt, G., Characterizations of transversal matroids and their presentations, J. Combin. Theory Ser. B, 12, 268-286 (1972) · Zbl 0219.05012
[8] Brylawski, T. H., An affine representation for transversal geometries, Stud. Appl. Math., 54, 143-160 (1975) · Zbl 0309.05018
[9] Crapo, H. H., Single-element extensions of matroids, J. Res. Natl. Bur. Stand. B, 69B, 55-65 (1965) · Zbl 0141.21701
[10] H.H. Crapo, W. Schmitt, A free subalgebra of the algebra of matroids (preprint); H.H. Crapo, W. Schmitt, A free subalgebra of the algebra of matroids (preprint) · Zbl 1071.05025
[11] Hopcroft, J.; Karp, R., An \(n^{5 / 2}\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225-231 (1973) · Zbl 0266.05114
[12] Ingleton, A. W., Transversal matroids and related structures, (Aigner, M., Higher Combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976) (1977), Reidel: Reidel Dordrecht, Boston, MA), 117-131 · Zbl 0379.05017
[13] Jensen, P. M.; Korte, B., Complexity of matroid property algorithms, SIAM J. Comput., 11, 184-190 (1982) · Zbl 0478.68044
[14] Matthews, L., Bicircular matroids, Q. J. Math. Oxford Ser. (2), 28, 213-227 (1977) · Zbl 0386.05022
[15] A. de Mier, M. Noy, A solution to the tennis ball problem, Theoret. Comput. Sci. (in press); A. de Mier, M. Noy, A solution to the tennis ball problem, Theoret. Comput. Sci. (in press) · Zbl 1078.05006
[16] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[17] Oxley, J. G.; Prendergast, K.; Row, D., Matroids whose ground sets are domains of functions, J. Aust. Math. Soc. Ser. A, 32, 380-387 (1982) · Zbl 0485.05023
[18] Sohoni, M., Rapid mixing of some linear matroids and other combinatorial objects, Graphs Combin., 15, 93-107 (1999) · Zbl 0954.05015
[19] Welsh, D. J.A., A bound for the number of matroids, J. Combin. Theory, 6, 313-316 (1969) · Zbl 0167.01704
[20] Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London, New York · Zbl 0343.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.