## Minimal free resolutions of the $G$-parking function ideal and the toppling ideal

HTML articles powered by AMS MathViewer

- by Madhusudan Manjunath, Frank-Olaf Schreyer and John Wilmes PDF
- Trans. Amer. Math. Soc.
**367**(2015), 2853-2874 Request permission

## Abstract:

The $G$-parking function ideal $M_G$ of a directed multigraph $G$ is a monomial ideal which encodes some of the combinatorial information of $G$. It is an initial ideal of the toppling ideal $I_G$, a lattice ideal intimately related to the chip-firing game on a graph. Both ideals were first studied by Cori, Rossin, and Salvy. A minimal free resolution for $M_G$ was given by Postnikov and Shapiro in the case when $G$ is saturated, i.e., whenever there is at least one edge $(u,v)$ for every ordered pair of distinct vertices $u$ and $v$. They also raised the problem of an explicit description of the minimal free resolution in the general case. In this paper, we give a minimal free resolution of $M_G$ for any undirected multigraph $G$, as well as for a family of related ideals including the toppling ideal $I_G$. This settles a conjecture of Manjunath and Sturmfels, as well as a conjecture of Perkinson and Wilmes.## References

- Omid Amini and Madhusudan Manjunath,
*Riemann-Roch for sub-lattices of the root lattice $A_n$*, Electron. J. Combin.**17**(2010), no. 1, Research Paper 124, 50. MR**2729373** - Matthew Baker and Serguei Norine,
*Riemann-Roch and Abel-Jacobi theory on a finite graph*, Adv. Math.**215**(2007), no. 2, 766–788. MR**2355607**, DOI 10.1016/j.aim.2007.04.012 - Matthew Baker and Farbod Shokrieh,
*Chip-firing games, potential theory on graphs, and spanning trees*, J. Combin. Theory Ser. A**120**(2013), no. 1, 164–182. MR**2971705**, DOI 10.1016/j.jcta.2012.07.011 - Brian Benson, Deeparnab Chakrabarty, and Prasad Tetali,
*$G$-parking functions, acyclic orientations and spanning trees*, Discrete Math.**310**(2010), no. 8, 1340–1353. MR**2592488**, DOI 10.1016/j.disc.2010.01.002 - 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 - Anton Dochtermann and Ramal Sanyal,
*Laplacian ideals, arrangements, and resolutions*, J. Algebr. Comb. (2012), 1–18, DOI 10.1007/s10801-014-0508-7. - David Eisenbud,
*Commutative algebra*, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR**1322960**, DOI 10.1007/978-1-4612-5350-1 - Eric Goles and Erich Prisner,
*Source reversal and chip firing on graphs*, Theoret. Comput. Sci.**233**(2000), no. 1-2, 287–295. MR**1732191**, DOI 10.1016/S0304-3975(99)00122-X - Daniel R. Grayson and Michael E. Stillman,
*Macaulay2, a software system for research in algebraic geometry*, Available at http://www.math.uiuc.edu/Macaulay2/. - Joe Harris,
*Algebraic geometry*, Graduate Texts in Mathematics, vol. 133, Springer-Verlag, New York, 1995. A first course; Corrected reprint of the 1992 original. MR**1416564** - Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson,
*Chip-firing and rotor-routing on directed graphs*, In and out of equilibrium. 2, Progr. Probab., vol. 60, Birkhäuser, Basel, 2008, pp. 331–364. MR**2477390**, DOI 10.1007/978-3-7643-8786-0_{1}7 - Sam Hopkins,
*Another proof of Wilmes’ conjecture*, Discrete Math.**323**(2014), 43–48. MR**3166053**, DOI 10.1016/j.disc.2014.01.010 - Horia Mania,
*Wilmes’ conjecture and boundary divisors*, arXiv:1210.8109 (2012). - Madhusudan Manjunath and Bernd Sturmfels,
*Monomials, binomials and Riemann-Roch*, J. Algebraic Combin.**37**(2013), no. 4, 737–756. MR**3047017**, DOI 10.1007/s10801-012-0386-9 - Ezra Miller and Bernd Sturmfels,
*Combinatorial commutative algebra*, Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005. MR**2110098** - Fatemeh Mohammadi and Farbod Shokrieh,
*Divisors on graphs, connected flags, and syzygies*, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math. Theor. Comput. Sci. Proc., AS, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2013, pp. 885–896 (English, with English and French summaries). MR**3091049** - David Perkinson, Jacob Perlman, and John Wilmes,
*Primer for the algebraic geometry of sandpiles*, Tropical and non-Archimedean geometry, Contemp. Math., vol. 605, Amer. Math. Soc., Providence, RI, 2013, pp. 211–256. MR**3204273**, DOI 10.1090/conm/605/12117 - Alexander Postnikov and Boris Shapiro,
*Trees, parking functions, syzygies, and deformations of monomial ideals*, Trans. Amer. Math. Soc.**356**(2004), no. 8, 3109–3142. MR**2052943**, DOI 10.1090/S0002-9947-04-03547-0 - W. A. Stein et al.,
*Sage Mathematics Software (Version 5.0)*, The Sage Development Team, 2012, http://www.sagemath.org. - Mauricio Velasco,
*Minimal free resolutions that are not supported by a CW-complex*, J. Algebra**319**(2008), no. 1, 102–114. MR**2378063**, DOI 10.1016/j.jalgebra.2007.10.011 - John Wilmes,
*Algebraic invariants of sandpile graphs*, Bachelor’s thesis, Reed College, 2010.

## Additional Information

**Madhusudan Manjunath**- Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
- Email: mmanjunath3@math.gatech.edu
**Frank-Olaf Schreyer**- Affiliation: Mathematik und Informatik, Universität des Saarlanes, 66123 Saarbrucken, Germany
- MR Author ID: 156975
- Email: schreyer@math.uni-sb.de
**John Wilmes**- Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637
- Email: wilmesj@math.uchicago.edu
- Received by editor(s): January 8, 2013
- Received by editor(s) in revised form: May 14, 2013
- Published electronically: September 24, 2014
- Additional Notes: Part of the work on this project was done while the first author was affiliated with Fachrichtung Mathematik, Universität des Saarlandes, Germany.

The third author was supported in part by NSF Grant No. DGE 1144082. - © Copyright 2014
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc.
**367**(2015), 2853-2874 - MSC (2010): Primary 13D02; Secondary 05C25
- DOI: https://doi.org/10.1090/S0002-9947-2014-06248-X
- MathSciNet review: 3301884