## Trees, parking functions, syzygies, and deformations of monomial ideals

HTML articles powered by AMS MathViewer

- by Alexander Postnikov and Boris Shapiro PDF
- Trans. Amer. Math. Soc.
**356**(2004), 3109-3142 Request permission

## Abstract:

For a graph $G$, we construct two algebras whose dimensions are both equal to the number of spanning trees of $G$. One of these algebras is the quotient of the polynomial ring modulo certain monomial ideal, while the other is the quotient of the polynomial ring modulo certain powers of linear forms. We describe the set of monomials that forms a linear basis in each of these two algebras. The basis elements correspond to $G$-parking functions that naturally came up in the abelian sandpile model. These ideals are instances of the general class of monotone monomial ideals and their deformations. We show that the Hilbert series of a monotone monomial ideal is always bounded by the Hilbert series of its deformation. Then we define an even more general class of monomial ideals associated with posets and construct free resolutions for these ideals. In some cases these resolutions coincide with Scarf resolutions. We prove several formulas for Hilbert series of monotone monomial ideals and investigate when they are equal to Hilbert series of deformations. In the appendix we discuss the abelian sandpile model.## References

- Dave Bayer, Irena Peeva, and Bernd Sturmfels,
*Monomial resolutions*, Math. Res. Lett.**5**(1998), no. 1-2, 31–46. MR**1618363**, DOI 10.4310/MRL.1998.v5.n1.a3 - Dave Bayer and Bernd Sturmfels,
*Cellular resolutions of monomial modules*, J. Reine Angew. Math.**502**(1998), 123–140. MR**1647559**, DOI 10.1515/crll.1998.083 - Robert Cori, Dominique Rossin, and Bruno Salvy,
*Polynomial ideals for sandpiles and their Gröbner bases*, Theoret. Comput. Sci.**276**(2002), no. 1-2, 1–15. MR**1896344**, DOI 10.1016/S0304-3975(00)00397-2 - Deepak Dhar,
*Self-organized critical state of sandpile automaton models*, Phys. Rev. Lett.**64**(1990), no. 14, 1613–1616. MR**1044086**, DOI 10.1103/PhysRevLett.64.1613 - J. Emsalem and A. Iarrobino,
*Inverse system of a symbolic power. I*, J. Algebra**174**(1995), no. 3, 1080–1090. MR**1337186**, DOI 10.1006/jabr.1995.1168 - Andrei Gabrielov,
*Abelian avalanches and Tutte polynomials*, Phys. A**195**(1993), no. 1-2, 253–274. MR**1215018**, DOI 10.1016/0378-4371(93)90267-8 - A. Gabrielov: Asymmetric abelian avalanches and sandpile, preprint 93-65, MSI, Cornell University, 1993.
- Vesselin Gasharov, Irena Peeva, and Volkmar Welker,
*The lcm-lattice in monomial resolutions*, Math. Res. Lett.**6**(1999), no. 5-6, 521–532. MR**1739211**, DOI 10.4310/MRL.1999.v6.n5.a5 - E. V. Ivashkevich, V. B. Priezzhev: Introduction to the sandpile model,
*Physica A 254*(1998), 97–116. - Victor G. Kac,
*Infinite-dimensional Lie algebras*, 3rd ed., Cambridge University Press, Cambridge, 1990. MR**1104219**, DOI 10.1017/CBO9780511626234 - G. Kreweras,
*Une famille de polynômes ayant plusieurs propriétés énumeratives*, Period. Math. Hungar.**11**(1980), no. 4, 309–320 (French). MR**603398**, DOI 10.1007/BF02107572 - R. Meester, F. Redig, and D. Znamenski,
*The abelian sandpile: a mathematical introduction*, Markov Process. Related Fields**7**(2001), no. 4, 509–523. MR**1893138** - Ezra Miller, Bernd Sturmfels, and Kohji Yanagawa,
*Generic and cogeneric monomial ideals*, J. Symbolic Comput.**29**(2000), no. 4-5, 691–708. Symbolic computation in algebra, analysis, and geometry (Berkeley, CA, 1998). MR**1769661**, DOI 10.1006/jsco.1999.0290 - Hiroshi Narushima,
*Principle of inclusion-exclusion on partially ordered sets*, Discrete Math.**42**(1982), no. 2-3, 243–250. MR**677057**, DOI 10.1016/0012-365X(82)90221-7 - I. M. Pak and A. E. Postnikov,
*Resolvents for $S_n$-modules that correspond to skew hooks, and combinatorial applications*, Funktsional. Anal. i Prilozhen.**28**(1994), no. 2, 72–75 (Russian); English transl., Funct. Anal. Appl.**28**(1994), no. 2, 132–134. MR**1283260**, DOI 10.1007/BF01076506 - Richard P. Stanley and Jim Pitman,
*A polytope related to empirical distributions, plane trees, parking functions, and the associahedron*, Discrete Comput. Geom.**27**(2002), no. 4, 603–634. MR**1902680**, DOI 10.1007/s00454-002-2776-6 - Alexander Postnikov, Boris Shapiro, and Mikhail Shapiro,
*Algebras of curvature forms on homogeneous manifolds*, Differential topology, infinite-dimensional Lie algebras, and applications, Amer. Math. Soc. Transl. Ser. 2, vol. 194, Amer. Math. Soc., Providence, RI, 1999, pp. 227–235. MR**1729365**, DOI 10.1090/trans2/194/10 - A. Postnikov, B. Shapiro, M. Shapiro: Chern forms on flag manifolds and forests,
*Proceedings of the 10-th International Conference on Formal Power Series and Algebraic Combinatorics,*FPSAC’98, Fields Institute, Toronto, 1998. - H. Schenck: Linear series on a special rational surface, preprint dated April 5, 2002.
- Boris Shapiro and Mikhail Shapiro,
*On ring generated by Chern $2$-forms on $\textrm {SL}_n/B$*, C. R. Acad. Sci. Paris Sér. I Math.**326**(1998), no. 1, 75–80 (English, with English and French summaries). MR**1649493**, DOI 10.1016/S0764-4442(97)82716-4 - Richard P. Stanley,
*Enumerative combinatorics. Vol. 1*, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR**1442260**, DOI 10.1017/CBO9780511805967 - Richard P. Stanley,
*Enumerative combinatorics. Vol. 2*, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR**1676282**, DOI 10.1017/CBO9780511609589 - Catherine Huafei Yan,
*On the enumeration of generalized parking functions*, Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000), 2000, pp. 201–209. MR**1818000**

## Additional Information

**Alexander Postnikov**- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- Email: apost@math.mit.edu
**Boris Shapiro**- Affiliation: Department of Mathematics, University of Stockholm, Stockholm, S-10691, Sweden
- MR Author ID: 212628
- Email: shapiro@matematik.su.se
- Received by editor(s): January 20, 2003
- Published electronically: March 12, 2004
- Additional Notes: The first author was supported in part by NSF grant DMS-0201494
- © Copyright 2004 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**356**(2004), 3109-3142 - MSC (2000): Primary 05C05; Secondary 05A99, 13D02, 13P99
- DOI: https://doi.org/10.1090/S0002-9947-04-03547-0
- MathSciNet review: 2052943