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

Postnikov, Alexander; Shapiro, Boris

doi:10.1090/S0002-9947-04-03547-0

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