On power ideals of transversal matroids and their “parking functions”
Algebraic Combinatorics, Volume 2 (2019) no. 4, p. 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.

Received : 2018-05-28
Revised : 2018-12-13
Accepted : 2018-12-25
Published online : 2019-08-01
DOI : https://doi.org/10.5802/alco.57
Classification:  05E40,  05E45,  05B35,  52B40
Keywords: transversal matroids, power ideals, polymatroids, parking functions
@article{ALCO_2019__2_4_573_0,
     author = {Sarmiento, Camilo},
     title = {On power ideals of transversal matroids and their ``parking functions''},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {2},
     number = {4},
     year = {2019},
     pages = {573-583},
     doi = {10.5802/alco.57},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_4_573_0}
}
On power ideals of transversal matroids and their “parking functions”. Algebraic Combinatorics, Volume 2 (2019) no. 4, pp. 573-583. doi : 10.5802/alco.57. https://alco.centre-mersenne.org/item/ALCO_2019__2_4_573_0/

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

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

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

[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 | Article | MR 316281 | Zbl 0263.05031

[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 | Article | MR 2971705 | Zbl 1408.05089

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

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

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

[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 | Article | MR 3262195 | Zbl 1309.05188

[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 | Article | MR 825481 | Zbl 0545.41018

[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 | Article | MR 1084708 | Zbl 0678.41009

[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) | Article | MR 2492449 | Zbl 1181.41011

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

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

[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 | Article | MR 2793025 | Zbl 1223.13010

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

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

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

[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 | Article | MR 3489059 | Zbl 1336.05060

[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 3104512 | Zbl 1295.52017

[22] Oxley, J. Matroid theory, Oxford University Press, Oxford, Oxford Graduate Texts in Mathematics, Volume 21 (2011), xiv+684 pages | Article | MR 2849819 | Zbl 1254.05002

[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 | Article | MR 2052943 | Zbl 1043.05038

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

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

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