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

DOI:
https://doi.org/10.1090/S0002-9947-04-03547-0

Published electronically:
March 12, 2004

MathSciNet review:
2052943

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For a graph , we construct two algebras whose dimensions are both equal to the number of spanning trees of . 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 -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.

**[BPS]**D. BAYER, I. PEEVA, B. STURMFELS: Monomial resolutions,*Mathematical Research Letters*(1998), 31-46. MR**5****99c:13029****[BaSt]**D. BAYER, B. STURMFELS: Cellular resolutions of monomial modules,*Journal für die Reine und Angewandte Mathematik*(1998), 123-140. MR**502****99g:13018****[CRS]**R. CORI, D. ROSSIN, B. SALVY: Polynomial ideals for sandpiles and their Gröbner bases,*Theoretical Computer Science*(2002), no. 1-2, 1-15. MR**276****2003b:13041****[Dhar]**D. DHAR: Self-organised critical state of the sandpile automaton models,*Physical Review Letters*(1990), no. 14, 1613-1616. MR**64****90m:82053****[EmIa]**I. EMSALEM, A. IARROBINO: Inverse system of a symbolic power I.*Journal of Algebra*(1995), no. 3, 1080-1090. MR**174****96i:13017****[Gab1]**A. GABRIELOV: Abelian avalanches and Tutte polynomials,*Physica A*(1993), 253-274. MR**195****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*(1999), no. 5-6, 521-532. MR**6****2001e:13018****[IvPr]**E. V. IVASHKEVICH, V. B. PRIEZZHEV: Introduction to the sandpile model,*Physica A*(1998), 97-116.**254****[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*(1980), no. 4, 309-320. MR**11****82f:05007****[MRZ]**R. MEESTER, F. REDIG, D. ZNAMENSKI: The abelian sandpile: a mathematical introduction,*Markov Process. Related Fields*(2001), no. 4, 509-523. MR**7****2003f:60175****[MSY]**E. MILLER, B. STURMFELS, K. YANAGAWA: Generic and cogeneric monomial ideals,*Journal of Symbolic Computation*(2000), no. 4-5, 691-708. MR**29****2001m:13051****[Naru]**H. NARUSHIMA: Principle of inclusion-exclusion on partially ordered sets,*Discrete Mathematics*(1982), 243-250. MR**42****83k:06004****[PP]**I. M. PAK, A. E. POSTNIKOV: Resolutions for -modules corresponding to skew hooks, and combinatorial applications,*Functional Analysis and its Applications*(1994), no. 2, 132-134. MR**28****95c:20020****[PiSt]**J. PITMAN, R. STANLEY: A polytope related to empirical distributions, plane trees, parking functions, and the associahedron,*Discrete and Computational Geometry*(2002), 603-634. MR**27****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*(1999), 227-235. MR**194****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 ,*C. R. Acad. Sci. Paris Sér. I Math.*(1998), is. 1, 75-80. MR**326****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*(2000), 201-209. MR**147****2002a:05017**

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

Email:
apost@math.mit.edu

**Boris Shapiro**

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

Email:
shapiro@matematik.su.se

DOI:
https://doi.org/10.1090/S0002-9947-04-03547-0

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