Facial structures of lattice path matroid polytopes. (English) Zbl 1430.52016

Summary: A lattice path matroid is a transversal matroid corresponding to a pair of lattice paths on the plane. A matroid base polytope is the polytope whose vertices are the incidence vectors of the bases of the given matroid. In this paper, we study the facial structures of matroid base polytopes corresponding to lattice path matroids. In the case of a border strip, we show that all faces of a lattice path matroid polytope can be described by certain subsets of deletions, contractions, and direct sums. In particular, we express them in terms of the lattice path obtained from the border strip. Subsequently, the facial structures of a lattice path matroid polytope for a general case are explained in terms of certain tilings of skew shapes inside the given region.


52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
05B35 Combinatorial aspects of matroids and geometric lattices
05A15 Exact enumeration problems, generating functions
Full Text: DOI arXiv


[1] Ardila, F.; Rincón, F.; Williams, L., Positroids and non-crossing partitions, Trans. Amer. Math. Soc., 368, 1, 337-363 (2016) · Zbl 1325.05015
[2] H. Bidkhori, Lattice Path Matroid Polytopes, 2012. arXiv:1212.5705.
[3] Bonin, J. E., Lattice path matroids: the excluded minors, J. Combin. Theory Ser. B, 100, 6, 585-599 (2010) · Zbl 1231.05054
[4] Bonin, J. E.; Giménez, O., Multi-path matroids, Combin. Probab. Comput., 16, 2, 193-217 (2007) · Zbl 1121.05023
[5] Bonin, J. E.; de Mier, A., Lattice path matroids: structural properties, European J. Combin., 27, 5, 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, 1, 63-94 (2003) · Zbl 1031.05031
[7] Borovik, A. V.; Gelfand, I. M.; White, N., (Coxeter Matroids. Coxeter Matroids, Progress in Mathematics, vol. 216 (2003), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston, MA), xxii+264 · Zbl 1050.52005
[8] Delucchi, E.; Dlugosch, M., Bergman complexes of lattice path matroids, SIAM J. Discrete Math., 29, 4, 1916-1930 (2015) · Zbl 1323.05028
[9] Edmonds, J., Submodular functions, matroids, and certain polyhedra, (Combinatorial Optimization—Eureka, You Shrink!. Combinatorial Optimization—Eureka, You Shrink!, Lecture Notes in Comput. Sci., vol. 2570 (2003), Springer: Springer Berlin), 11-26 · Zbl 1024.90054
[10] Edmonds, J.; Fulkerson, D. R., Transversals and matroid partition, J. Res. Nat. Bur. Standards Sect. B, 69B, 147-153 (1965) · Zbl 0141.21801
[11] Feichtner, E. M.; Sturmfels, B., Matroid polytopes, nested sets and Bergman fans, Port. Math., 62, 4, 437-468 (2005) · Zbl 1092.52006
[12] Gelf́and, I. M.; Goresky, R. M.; MacPherson, R. D.; Serganova, V. V., Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. Math., 63, 3, 301-316 (1987) · Zbl 0622.57014
[13] 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., 60, 3, 698-719 (2018) · Zbl 1494.52014
[14] Knauer, K.; Martínez-Sandoval, L.; Ramírez Alfonsín, J. L., A Tutte polynomial inequality for lattice path matroids, Adv. Appl. Math., 94, 23-38 (2018) · Zbl 1377.05089
[15] 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
[16] Oh, S., Generalized permutohedra, \(h\)-vectors of cotransversal matroids and pure O-sequences, Electron. J. Combin., 20, 3 (2013), Paper 14, 14 · Zbl 1295.52017
[17] Postnikov, A., Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN, 6, 1026-1106 (2009) · Zbl 1162.52007
[18] Postnikov, A.; Reiner, V.; Williams, L., Faces of generalized permutohedra, Doc. Math., 13, 207-273 (2008) · Zbl 1167.05005
[19] Schrijver, A., (Combinatorial optimization. Polyhedra and efficiency. Vol. C. Combinatorial optimization. Polyhedra and efficiency. Vol. C, Algorithms and Combinatorics, vol. 24 (2003), Springer-Verlag: Springer-Verlag Berlin), 70-83, Disjoint paths, hypergraphs, (Chapters) · Zbl 1041.90001
[20] Schweig, J., On the \(h\)-vector of a lattice path matroid, Electron. J. Combin., 17, 1 (2010), Note 3, 6 · Zbl 1267.05057
[21] Schweig, J., Toric ideals of lattice path matroids and polymatroids, J. Pure Appl. Algebra, 215, 11, 2660-2665 (2011) · Zbl 1230.13028
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.