Delta-matroids as subsystems of sequences of Higgs lifts. (English) Zbl 1461.05025

Summary: É. Tardos [in: Matroid theory. Proceedings of the colloquium on matroid theory held in Szeged, Hungary, August 29 – September 4, 1982. Amsterdam etc.: North-Holland; Budapest: János Bolyai Mathematical Society. 359–382 (1985; Zbl 0602.05020)] studied special delta-matroids obtained from sequences of Higgs lifts; these are the full Higgs lift delta-matroids that we treat and around which all of our results revolve. We give an excluded-minor characterization of the class of full Higgs lift delta-matroids within the class of all delta-matroids, and we give similar characterizations of two other minor-closed classes of delta-matroids that we define using Higgs lifts. We introduce a minor-closed, dual-closed class of Higgs lift delta-matroids that arise from lattice paths. It follows from results of A. Bouchet [in: Combinatorics. Proceedings of the 7th Hungarian colloquium held from July 5 to July 10, 1987 in Eger, Hungary. Amsterdam etc.: North-Holland; Budapest: János Bolyai Mathematical Society. 167–182 (1988; Zbl 0708.05013)] that all delta-matroids can be obtained from full Higgs lift delta-matroids by removing certain feasible sets; to address which feasible sets can be removed, we give an excluded-minor characterization of delta-matroids within the more general structure of set systems. Many of these excluded minors occur again when we characterize the delta-matroids in which the collection of feasible sets is the union of the collections of bases of matroids of different ranks, and yet again when we require those matroids to have special properties, such as being paving.


05B35 Combinatorial aspects of matroids and geometric lattices
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
05C83 Graph minors
Full Text: DOI arXiv Link


[1] An, S.; Jung, J.; Kim, S., Facial structures of lattice path matroid polytopes, preprint · Zbl 1430.52016
[2] Bansal, N.; Pendavingh, R. A.; van der Pol, J. G., On the number of matroids, Combinatorica, 35, 253-277 (2015) · Zbl 1363.05005
[3] Bonin, J., Lattice path matroids: the excluded minors, J. Combin. Theory Ser. B, 100, 585-599 (2010) · Zbl 1231.05054
[4] Bonin, J.; Giménez, O., Multi-path matroids, Combin. Probab. Comput., 16, 193-217 (2007) · Zbl 1121.05023
[5] Bonin, J.; de Mier, A., Lattice path matroids: structural properties, European J. Combin., 27, 701-738 (2006) · Zbl 1087.05014
[6] 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
[7] Bonin, J.; Schmitt, W., Splicing matroids, European J. Combin., 32, 722-744 (2011) · Zbl 1229.05061
[8] Bouchet, A., Greedy algorithm and symmetric matroids, Math. Program., 38, 147-159 (1987) · Zbl 0633.90089
[9] Bouchet, A., Maps and delta-matroids, Discrete Math., 78, 59-71 (1989) · Zbl 0719.05019
[10] Bouchet, A., Representability of Δ-matroids, (Proceedings of the 6th Hungarian Colloquium of Combinatorics. Proceedings of the 6th Hungarian Colloquium of Combinatorics, Colloq. Math. Soc. János Bolyai (1987)), 167-182
[11] Bouchet, A., Multimatroids II. Orthogonality, minors and connectivity, Electron. J. Combin., 5, Article 8 pp. (1998) · Zbl 0885.05050
[12] Bouchet, A.; Duchamp, A., Representability of delta-matroids over GF(2), Linear Algebra Appl., 146, 67-78 (1991) · Zbl 0738.05027
[13] Brylawski, T. H., Constructions, (White, N., Theory of Matroids (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 127-223
[14] Chun, C.; Moffatt, I.; Noble, S. D.; Rueckriemen, R., Matroids, delta-matroids and embedded graphs, preprint · Zbl 1417.05103
[15] Chun, C.; Moffatt, I.; Noble, S. D.; Rueckriemen, R., On the interplay between embedded graphs and delta-matroids, Proc. Lond. Math. Soc., 118, 675-700 (2019) · Zbl 1410.05029
[16] Cohen, E.; Tetali, P.; Yeliussizov, D., Lattice path matroids: negative correlation and fast mixing, preprint
[17] Delucchi, E.; Dlugosch, M., Bergman complexes of lattice path matroids, SIAM J. Discrete Math., 29, 1916-1930 (2015) · Zbl 1323.05028
[18] Dupont, C.; Fink, A.; Moci, L., Universal Tutte characters via combinatorial coalgebras, J. Algebraic Combin., 1, 603-651 (2018) · Zbl 1433.16037
[19] Eu, S.; Lo, Y.; Tsai, Y., Toric g-polynomials of hook shape lattice path matroid polytopes and product of simplices, preprint
[20] Funk, D.; Mayhew, D.; Noble, S., How many delta-matroids are there? preprint, European J. Combin., 69, 149-158 (2018) · Zbl 1376.05031
[21] Knauer, K.; Martínez-Sandoval, L.; Ramírez Alfonsín, J. L., On lattice path matroid polytopes: integer points and Ehrhart polynomial, Discrete Comput. Geom. (2018) · Zbl 1494.52014
[22] Knauer, K.; Martínez-Sandoval, L.; Alfonsín, J. L. Ramírez, A Tutte polynomial inequality for lattice path matroids, Adv. in Appl. Math., 94, 23-38 (2018) · Zbl 1377.05089
[23] Kung, J. P.S., Strong maps, (White, N., Theory of Matroids (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 224-253
[24] Mayhew, D.; Newman, M.; Welsh, D.; Whittle, G., On the asymptotic proportion of connected matroids, European J. Combin., 32, 882-890 (2011) · Zbl 1244.05047
[25] de Mier, A.; Noy, M., A solution to the tennis ball problem, Theoret. Comput. Sci., 346, 254-264 (2005) · Zbl 1078.05006
[26] Morton, J.; Turner, J., Computing the Tutte polynomial of lattice path matroids using determinantal circuits, Theoret. Comput. Sci., 598, 150-156 (2015) · Zbl 1329.68120
[27] Oxley, James G., Matroid Theory (2011), Oxford University Press: Oxford University Press Oxford · Zbl 1254.05002
[28] Schweig, J., Toric ideals of lattice path matroids and polymatroids, J. Pure Appl. Algebra, 215, 2660-2665 (2011) · Zbl 1230.13028
[29] Schweig, J., On the h-vector of a lattice path matroid, Electron. J. Combin., 17, Article 3 pp. (2010)
[30] Tardos, E., Generalized matroids and supermodular colourings, (Matroid Theory. Matroid Theory, Szeged, 1982 (1985), North-Holland: North-Holland Amsterdam), 359-382
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.