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

By Alexander Postnikov, Boris Z. Shapiro. 2003

201 citations recorded by the source corpus.

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.

Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/8559c39f000d2934cd188b5dc08f4d7ece024ea9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Zonotopal algebra (2007, background): “Let us now illustrate connections with algebraic graph theory and with the notion of parking functions from combinatorics (see [34], [45], [29]).”
Stellahedral geometry of matroids (2022, unknown): “We denote by”
PRIMER FOR THE ALGEBRAIC GEOMETRY OF SANDPILES (2011, background): “A G-parking function [28] (with respect to s) is a function f : V → Z such that there exists a superstable configuration c on G with the property that f(v) = cv for v ∈ Ṽ and f(s) = −1.”
Riemann–Roch and Abel–Jacobi theory on a finite graph (2006, methodology): “)+1−gas desired.12 MATTHEW BAKER AND SERGUEI NORINE 3. Riemann-Roch for graphs 3.1. G-parking functions and reduced divisors. In this section, we use the notion of a G-parking function, introduced in [33], to deﬁne a unique reduced divisor in each equivalence class in Div(G). Reduced divisors will p”
Ordered set partitions, generalized coinvariant algebras, and the Delta Conjecture (2016, unknown): “q) (after applying ω and an appropriate change of variables). In the case k = n Berget and Rhoades [6] proved that the restriction to Sn of a graded Sn+1- module V (n) deﬁned by Postnikov and Shapiro [26] solves Problem 7.7. The module V(n) is deﬁned in a matroid-theoretic fashion involving subgraph”