Standard complexes of matroids and lattice paths. (English) Zbl 1493.05300

Engström, Alexander; Sanyal, Raman; Stump, Christian

Vietnam J. Math. 50, No. 3, 763-779 (2022).

A matroid is a combinatorial structure that abstracts and generalizes the notion of dependence in graphs and vector spaces. Matroids come with a rich enumerative theory and have found applications in geometry, topology, combinatorial optimization, network theory, and coding theory. In this article, the authors define and study a new class of simpicial complexes, called standard compelxes, associated to a matroid. The motivation behind the study of these complexes comes from the Groöbner basis theory for finite point configurations. The standard compelxes are certain subcomplexes of the independence complexes that are invariant under matroid duality. The authors prove that, for lexicographic term order, the standard compelxes satisfy a deletion-contraction-type recurrence. They also explicitly determine the lexicographic standard complexes for lattice path matroids.

Reviewer: Anurag Singh (Raipur)

MSC:

05E45	Combinatorial aspects of simplicial complexes
13P10	Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13P25	Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
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.)

Keywords:

standard monomials; simplicial complexes; lattice path matroids

Software:

FindStat

References:

[1]	Ardila, F., The Catalan matroid, J. Combin. Theory Ser. A, 104, 49-62 (2003) · Zbl 1031.05030 · doi:10.1016/S0097-3165(03)00121-3
[2]	Anstee, RP; Rónyai, L.; Sali, A., Shattering news, Gr. Combin., 18, 59-73 (2002) · Zbl 0990.05123 · doi:10.1007/s003730200003
[3]	Bonin, JE; de Mier, A., Lattice path matroids: Structural properties, Eur. J. Combin., 27, 701-738 (2006) · Zbl 1087.05014 · doi:10.1016/j.ejc.2005.01.008
[4]	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 · doi:10.1016/S0097-3165(03)00122-5
[5]	Brylawski, T., The broken-circuit complex, Trans. Amer. Math. Soc., 234, 417-433 (1977) · Zbl 0368.05022 · doi:10.1090/S0002-9947-1977-0468931-6
[6]	Cox, DA; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms, 4th edn. (2015), Cham: Springer, Cham · Zbl 1335.13001 · doi:10.1007/978-3-319-16721-3
[7]	de Loera, JA, Gröbner bases and graph colorings, Beitr. Algebra Geom., 36, 89-96 (1995) · Zbl 0819.05029
[8]	Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), pp 69-87. Gordon and Breach, New York (1970) · Zbl 0268.05019
[9]	Elizalde, S.; Rubey, M., Symmetries of statistics on lattice paths between two boundaries, Adv. Math., 287, 347-388 (2016) · Zbl 1327.05338 · doi:10.1016/j.aim.2015.09.025
[10]	Grande, F.; Sanyal, R., Theta rank, levelness, and matroid minors, J. Combin. Theory Ser. B, 123, 1-31 (2017) · Zbl 1354.05020 · doi:10.1016/j.jctb.2016.11.002
[11]	Hegedűs, G.; Rónyai, L., Gröbner bases for complete uniform families, J. Algebraic Combin., 17, 171-180 (2003) · Zbl 1045.13011 · doi:10.1023/A:1022934815185
[12]	Knauer, K.; Martínez-Sandoval, L.; Alfonsín, JLR, On lattice path matroid polytopes: integer points and Ehrhart polynomial, Discrete Comput. Geom., 60, 698-719 (2018) · Zbl 1494.52014 · doi:10.1007/s00454-018-9965-4
[13]	Laurent, M., Semidefinite representations for finite varieties, Math. Program., 109, 1-26 (2007) · Zbl 1152.90007 · doi:10.1007/s10107-004-0561-4
[14]	Lederer, M., Finite sets of d-planes in affine space, J. Algebra, 321, 3827-3849 (2009) · Zbl 1191.14072 · doi:10.1016/j.jalgebra.2009.03.025
[15]	Lovász, L., Stable sets and polynomials, Discrete Math., 124, 137-153 (1994) · Zbl 0792.05082 · doi:10.1016/0012-365X(92)00057-X
[16]	Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra. Graduate Texts in Mathematics, vol. 227. Springer, New York (2005) · Zbl 1090.13001
[17]	Onn, S.; Sturmfels, B., Cutting corners, Adv. Appl. Math., 23, 29-48 (1999) · Zbl 0955.52008 · doi:10.1006/aama.1999.0645
[18]	Postnikov, A., Permutohedra, associahedra, and beyond, Int. Math. Res. Not., 2009, 1026-1106 (2009) · Zbl 1162.52007 · doi:10.1093/imrn/rnn153
[19]	Robbiano, L.: Gröbner bases and statistics. In: Buchberger, B., Winkler, F (eds.) Gröbner Bases and Applications. London Mathematical Society Lecture Note Series, vol. 251, pp 179-204. Cambridge University Press, Cambridge (1998) · Zbl 0907.62087
[20]	Rubey, M., Stump, C., et al.: FindStat - The combinatorial statistics database. http://www.FindStat.org, 2019. Accessed: December 2 (2021) · Zbl 1442.62004
[21]	Schweig, J., On the h-vector of a lattice path matroid, Electron. J. Combin., 17, 3 (2010) · Zbl 1267.05057 · doi:10.37236/452
[22]	Schweig, J., Toric ideals of lattice path matroids and polymatroids, J. Pure Appl. Algebra, 215, 2660-2665 (2011) · Zbl 1230.13028 · doi:10.1016/j.jpaa.2011.03.010
[23]	White, N. (ed.): Matroid Applications. Encyclopedia of Mathematics and its Applications, vol. 40. Cambridge University Press, Cambridge (1992) · Zbl 0742.00052