×

zbMATH — the first resource for mathematics

Trees, parking functions, syzygies, and deformations of monomial ideals. (English) Zbl 1043.05038
Summary: 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 a 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.

MSC:
05C05 Trees
05A99 Enumerative combinatorics
13D02 Syzygies, resolutions, complexes and commutative rings
13P99 Computational aspects and applications of commutative rings
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Dave Bayer, Irena Peeva, and Bernd Sturmfels, Monomial resolutions, Math. Res. Lett. 5 (1998), no. 1-2, 31 – 46. · Zbl 0909.13010 · doi:10.4310/MRL.1998.v5.n1.a3 · doi.org
[2] Dave Bayer and Bernd Sturmfels, Cellular resolutions of monomial modules, J. Reine Angew. Math. 502 (1998), 123 – 140. · Zbl 0909.13011 · doi:10.1515/crll.1998.083 · doi.org
[3] 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. · Zbl 1002.68105 · doi:10.1016/S0304-3975(00)00397-2 · doi.org
[4] Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613 – 1616. · Zbl 0943.82553 · doi:10.1103/PhysRevLett.64.1613 · doi.org
[5] J. Emsalem and A. Iarrobino, Inverse system of a symbolic power. I, J. Algebra 174 (1995), no. 3, 1080 – 1090. · Zbl 0842.14002 · doi:10.1006/jabr.1995.1168 · doi.org
[6] Andrei Gabrielov, Abelian avalanches and Tutte polynomials, Phys. A 195 (1993), no. 1-2, 253 – 274. · Zbl 0786.60124 · doi:10.1016/0378-4371(93)90267-8 · doi.org
[7] A. GABRIELOV: Asymmetric abelian avalanches and sandpile, preprint 93-65, MSI, Cornell University, 1993.
[8] Vesselin Gasharov, Irena Peeva, and Volkmar Welker, The lcm-lattice in monomial resolutions, Math. Res. Lett. 6 (1999), no. 5-6, 521 – 532. · Zbl 0970.13004 · doi:10.4310/MRL.1999.v6.n5.a5 · doi.org
[9] E. V. IVASHKEVICH, V. B. PRIEZZHEV: Introduction to the sandpile model, Physica A 254 (1998), 97-116.
[10] Victor G. Kac, Infinite-dimensional Lie algebras, 3rd ed., Cambridge University Press, Cambridge, 1990. · Zbl 0716.17022
[11] G. Kreweras, Une famille de polynômes ayant plusieurs propriétés énumeratives, Period. Math. Hungar. 11 (1980), no. 4, 309 – 320 (French). · Zbl 0423.05006 · doi:10.1007/BF02107572 · doi.org
[12] R. Meester, F. Redig, and D. Znamenski, The abelian sandpile: a mathematical introduction, Markov Process. Related Fields 7 (2001), no. 4, 509 – 523. · Zbl 0995.60094
[13] 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). · Zbl 0955.13008 · doi:10.1006/jsco.1999.0290 · doi.org
[14] Hiroshi Narushima, Principle of inclusion-exclusion on partially ordered sets, Discrete Math. 42 (1982), no. 2-3, 243 – 250. · Zbl 0497.06003 · doi:10.1016/0012-365X(82)90221-7 · doi.org
[15] I. M. Pak and A. E. Postnikov, Resolvents for \?_\?-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. · Zbl 0832.20016 · doi:10.1007/BF01076506 · doi.org
[16] 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. · Zbl 1012.52019 · doi:10.1007/s00454-002-2776-6 · doi.org
[17] 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. · Zbl 0971.53034 · doi:10.1090/trans2/194/10 · doi.org
[18] 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.
[19] H. SCHENCK: Linear series on a special rational surface, preprint dated April 5, 2002.
[20] Boris Shapiro and Mikhail Shapiro, On ring generated by Chern 2-forms on \?\?_\?/\?, C. R. Acad. Sci. Paris Sér. I Math. 326 (1998), no. 1, 75 – 80 (English, with English and French summaries). · Zbl 0944.53027 · doi:10.1016/S0764-4442(97)82716-4 · doi.org
[21] 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. · Zbl 0889.05001
[22] 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. · Zbl 0928.05001
[23] 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. · Zbl 0971.05003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.