On power ideals of transversal matroids and their “parking functions”

Sarmiento, Camilo

Algebraic Combinatorics, Tome 2 (2019) no. 4, pp. 573-583.

To a vector configuration one can associate a polynomial ideal generated by powers of linear forms, known as a power ideal, which exhibits many combinatorial features of the matroid underlying the configuration.

In this note we observe that certain power ideals associated to transversal matroids are, somewhat unexpectedly, monomial. Moreover, the (monomial) basis elements of the quotient ring defined by such a power ideal can be naturally identified with the lattice points of a remarkable convex polytope: a polymatroid, also known as generalized permutohedron. We dub the exponent vectors of these monomial basis elements “parking functions” of the corresponding transversal matroid.

We highlight the connection between our investigation and Stanley–Reisner theory, and relate our findings to Stanley’s conjectured necessary condition on matroid $h$-vectors.

Classification : 05E40, 05E45, 05B35, 52B40
Mots clés : transversal matroids, power ideals, polymatroids, parking functions

[1] Adiprasito, K.; Huh, J.; Katz, E. Hodge theory for combinatorial geometries, Ann. of Math. (2), Volume 188 (2018) no. 2, pp. 381-452 | DOI | MR | Zbl

[2] Ardila, F. Enumerative and algebraic aspects of matroids and hyperplane arrangements, Ph. D. Thesis, Massachusetts Institute of Technology (USA) (2003) | MR

[3] Ardila, F.; Postnikov, A. Combinatorics and geometry of power ideals, Trans. Amer. Math. Soc., Volume 362 (2010) no. 8, pp. 4357-4384 | DOI | MR | Zbl

[4] Atkin, A. O. L. Remark on a paper of Piff and Welsh, J. Comb. Theory, Ser. B, Volume 13 (1972) no. 2, pp. 179-182 | DOI | MR | Zbl

[5] Baker, M.; Shokrieh, F. Chip-firing games, potential theory on graphs, and spanning trees, J. Comb. Theory, Ser. A, Volume 120 (2013) no. 1, pp. 164-182 | DOI | MR | Zbl

[6] Berget, A. Products of linear forms and Tutte polynomials, European J. Combin., Volume 31 (2010) no. 7, pp. 1924-1935 | DOI | MR | Zbl

[7] Björner, A. Homology and shellability of matroids and geometric lattices, Matroid applications (Encyclopedia Math. Appl.), Volume 40, Cambridge Univ. Press, Cambridge, 1992, pp. 226-283 | DOI | MR | Zbl

[8] Brualdi, R. A. Transversal matroids, Combinatorial geometries (Encyclopedia Math. Appl.), Volume 29, Cambridge Univ. Press, Cambridge, 1987, pp. 72-97 | DOI | MR | Zbl

[9] Constantinescu, A.; Kahle, T.; Varbaro, M. Generic and special constructions of pure $O$-sequences, Bull. Lond. Math. Soc., Volume 46 (2014) no. 5, pp. 924-942 | DOI | MR | Zbl

[10] Dahmen, W.; Micchelli, C. A. On the local linear independence of translates of a box spline, Studia Math., Volume 82 (1985) no. 3, pp. 243-263 | DOI | MR | Zbl

[11] de Boor, C.; Dyn, N.; Ron, A. On two polynomial spaces associated with a box spline, Pacific J. Math., Volume 147 (1991) no. 2, pp. 249-267 | DOI | MR | Zbl

[12] De Concini, C.; Procesi, C. Hyperplane arrangements and box splines, Michigan Math. J., Volume 57 (2008), pp. 201-225 (With an appendix by A. Björner, Special volume in honor of Melvin Hochster) | DOI | MR | Zbl

[13] De Concini, C.; Procesi, C. Topics in hyperplane arrangements, polytopes and box-splines, Universitext, Springer, New York, 2010, xx+384 pages | DOI | Zbl

[14] Gawrilow, E.; Joswig, M. polymake: a framework for analyzing convex polytopes, Polytopes – combinatorics and computation (Oberwolfach, 1997) (DMV Sem.), Volume 29, Birkhäuser, Basel, 2000, pp. 43-73 | DOI | MR | Zbl

[15] Grayson, D. R.; Stillman, M. E. Macaulay2, a software system for research in algebraic geometry (Available at http://www.math.uiuc.edu/Macaulay2/)

[16] Holtz, O.; Ron, A. Zonotopal algebra, Adv. Math., Volume 227 (2011) no. 2, pp. 847-894 | DOI | MR | Zbl

[17] Huh, J. $h$-vectors of matroids and logarithmic concavity, Adv. Math., Volume 270 (2015), pp. 49-59 | DOI | MR | Zbl

[18] Lovász, L.; Plummer, M. D. Matching theory, North-Holland Mathematics Studies, 121, North-Holland Publishing Co., Amsterdam, 1986, xxvii+544 pages (Annals of Discrete Mathematics, 29) | MR | Zbl

[19] Merino, C. The chip firing game and matroid complexes, Discrete models: combinatorics, computation, and geometry (Paris, 2001) (Discrete Math. Theor. Comput. Sci. Proc.), Volume AA, Maison Inform. Math. Discrèt. (MIMD), Paris (2001), pp. 245-255 | MR | Zbl

[20] Mohammadi, F.; Shokrieh, F. Divisors on graphs, binomial and monomial ideals, and cellular resolutions, Math. Z., Volume 283 (2016) no. 1-2, pp. 59-102 | DOI | MR | Zbl

[21] Oh, S. Generalized permutohedra, $h$-vectors of cotransversal matroids and pure O-sequences, Electron. J. Combin., Volume 20 (2013) no. 3, P14, 14 pages | MR | Zbl

[22] Oxley, J. Matroid theory, Oxford Graduate Texts in Mathematics, 21, Oxford University Press, Oxford, 2011, xiv+684 pages | DOI | MR | Zbl

[23] Postnikov, A.; Shapiro, B. Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc., Volume 356 (2004) no. 8, pp. 3109-3142 | DOI | MR | Zbl

[24] Schrijver, A. Combinatorial optimization. Polyhedra and efficiency, Algorithms and Combinatorics, 24, Springer-Verlag, Berlin, 2003, p. i-xxxiv and 649–1217 (Vol. B, Matroids, trees, stable sets, Chapters 39–69) | MR | Zbl

[25] Stanley, R. P. Combinatorics and commutative algebra, Progress in Mathematics, 41, Birkhäuser Boston, Inc., Boston, MA, 1996, x+164 pages | MR | Zbl

[26] The Sage Developers SageMath, the Sage Mathematics Software System (Version 8.0) (2017) http://www.sagemath.org