Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

Authors: Alexander Postnikov and Boris Shapiro
Journal: Trans. Amer. Math. Soc. 356 (2004), 3109-3142
MSC (2000): Primary 05C05; Secondary 05A99, 13D02, 13P99
Published electronically: March 12, 2004
MathSciNet review: 2052943
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [BPS] D. BAYER, I. PEEVA, B. STURMFELS: Monomial resolutions, Mathematical Research Letters 5 (1998), 31-46. MR 99c:13029
  • [BaSt] D. BAYER, B. STURMFELS: Cellular resolutions of monomial modules, Journal für die Reine und Angewandte Mathematik 502 (1998), 123-140. MR 99g:13018
  • [CRS] R. CORI, D. ROSSIN, B. SALVY: Polynomial ideals for sandpiles and their Gröbner bases, Theoretical Computer Science 276 (2002), no. 1-2, 1-15. MR 2003b:13041
  • [Dhar] D. DHAR: Self-organised critical state of the sandpile automaton models, Physical Review Letters 64 (1990), no. 14, 1613-1616. MR 90m:82053
  • [EmIa] I. EMSALEM, A. IARROBINO: Inverse system of a symbolic power I. Journal of Algebra 174 (1995), no. 3, 1080-1090. MR 96i:13017
  • [Gab1] A. GABRIELOV: Abelian avalanches and Tutte polynomials, Physica A 195 (1993), 253-274. MR 94c:82085
  • [Gab2] A. GABRIELOV: Asymmetric abelian avalanches and sandpile, preprint 93-65, MSI, Cornell University, 1993.
  • [GPW] V. GASHAROV, I. PEEVA, V. WELKER: The lcm-lattice in monomial resolutions, Mathematical Research Letters 6 (1999), no. 5-6, 521-532. MR 2001e:13018
  • [IvPr] E. V. IVASHKEVICH, V. B. PRIEZZHEV: Introduction to the sandpile model, Physica A 254 (1998), 97-116.
  • [Kac] V. G. KAC: Infinite dimensional Lie algebras, third edition, Cambridge University Press, 1990. MR 92k:17038
  • [Krew] G. KREWERAS: Une famille de polynômes ayant plusieurs propriétés énumeratives, Periodica Mathematica Hungarica 11 (1980), no. 4, 309-320. MR 82f:05007
  • [MRZ] R. MEESTER, F. REDIG, D. ZNAMENSKI: The abelian sandpile: a mathematical introduction, Markov Process. Related Fields 7 (2001), no. 4, 509-523. MR 2003f:60175
  • [MSY] E. MILLER, B. STURMFELS, K. YANAGAWA: Generic and cogeneric monomial ideals, Journal of Symbolic Computation 29 (2000), no. 4-5, 691-708. MR 2001m:13051
  • [Naru] H. NARUSHIMA: Principle of inclusion-exclusion on partially ordered sets, Discrete Mathematics 42 (1982), 243-250. MR 83k:06004
  • [PP] I. M. PAK, A. E. POSTNIKOV: Resolutions for $S_n$-modules corresponding to skew hooks, and combinatorial applications, Functional Analysis and its Applications 28 (1994), no. 2, 132-134. MR 95c:20020
  • [PiSt] J. PITMAN, R. STANLEY: A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete and Computational Geometry 27 (2002), 603-634. MR 2003e:52017
  • [PSS1] A. POSTNIKOV, B. SHAPIRO, M. SHAPIRO: Algebras of curvature forms on homogeneous manifolds, in ``Differential Topology, Infinite-Dimensional Lie Algebras, and Applications: D. B. Fuchs 60th Anniversary Collection,'' AMS Translations, Ser. 2 194 (1999), 227-235. MR 2001a:53079
  • [PSS2] 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.
  • [Sche] H. SCHENCK: Linear series on a special rational surface, preprint dated April 5, 2002.
  • [ShSh] B. SHAPIRO, M. SHAPIRO: On algebra generated by Bott-Chern 2-forms on $\mathrm{SL}_n/\mathrm{B}$, C. R. Acad. Sci. Paris Sér. I Math. 326 (1998), is. 1, 75-80. MR 99g:14027
  • [Sta1] R. P. STANLEY: Enumerative Combinatorics, Volume 1, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge, 1997. MR 98a:05001
  • [Sta2] R. P. STANLEY: Enumerative Combinatorics, Volume 2, Cambridge Studies in Advanced Mathematics 62, Cambridge University Press, Cambridge, 1999. MR 2000k:05026
  • [Yan] C. H. YAN: On the enumeration of generalized parking functions, Proceedings of the 31-st Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000), Congressus Numerantium 147 (2000), 201-209. MR 2002a:05017

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05C05, 05A99, 13D02, 13P99

Retrieve articles in all journals with MSC (2000): 05C05, 05A99, 13D02, 13P99

Additional Information

Alexander Postnikov
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Boris Shapiro
Affiliation: Department of Mathematics, University of Stockholm, Stockholm, S-10691, Sweden

Keywords: Spanning tree, parking function, abelian sandpile model, monomial ideal, deformation, minimal free resolution, order complex, Hilbert series
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
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society