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)

 
 

 

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


Authors: Madhusudan Manjunath, Frank-Olaf Schreyer and John Wilmes
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
Published electronically: September 24, 2014
MathSciNet review: 3301884
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

  • [1] 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 (2012a:06009)
  • [2] 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 (2008m:05167), https://doi.org/10.1016/j.aim.2007.04.012
  • [3] 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, https://doi.org/10.1016/j.jcta.2012.07.011
  • [4] 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 (2011i:05152), https://doi.org/10.1016/j.disc.2010.01.002
  • [5] 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 (2003b:13041), https://doi.org/10.1016/S0304-3975(00)00397-2
  • [6] Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613-1616. MR 1044086 (90m:82053), https://doi.org/10.1103/PhysRevLett.64.1613
  • [7] Anton Dochtermann and Ramal Sanyal, Laplacian ideals, arrangements, and resolutions, J. Algebr. Comb. (2012), 1-18, DOI 10.1007/s10801-014-0508-7.
  • [8] David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960 (97a:13001)
  • [9] Eric Goles and Erich Prisner, Source reversal and chip firing on graphs, Theoret. Comput. Sci. 233 (2000), no. 1-2, 287-295. MR 1732191 (2000i:05084), https://doi.org/10.1016/S0304-3975(99)00122-X
  • [10] Daniel R. Grayson and Michael E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
  • [11] 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 (97e:14001)
  • [12] 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 (2010f:82066), https://doi.org/10.1007/978-3-7643-8786-0_17
  • [13] Sam Hopkins, Another proof of Wilmes' conjecture, Discrete Math. 323 (2014), 43-48. MR 3166053, https://doi.org/10.1016/j.disc.2014.01.010
  • [14] Horia Mania, Wilmes' conjecture and boundary divisors, arXiv:1210.8109 (2012).
  • [15] Madhusudan Manjunath and Bernd Sturmfels, Monomials, binomials and Riemann-Roch, J. Algebraic Combin. 37 (2013), no. 4, 737-756. MR 3047017, https://doi.org/10.1007/s10801-012-0386-9
  • [16] Ezra Miller and Bernd Sturmfels, Combinatorial commutative algebra, Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005. MR 2110098 (2006d:13001)
  • [17] 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
  • [18] 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, https://doi.org/10.1090/conm/605/12117
  • [19] Alexander Postnikov and Boris Shapiro, Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc. 356 (2004), no. 8, 3109-3142 (electronic). MR 2052943 (2005a:05066), https://doi.org/10.1090/S0002-9947-04-03547-0
  • [20] W.A. Stein et al., Sage Mathematics Software (Version 5.0), The Sage Development Team, 2012, http://www.sagemath.org.
  • [21] Mauricio Velasco, Minimal free resolutions that are not supported by a CW-complex, J. Algebra 319 (2008), no. 1, 102-114. MR 2378063 (2008j:13028), https://doi.org/10.1016/j.jalgebra.2007.10.011
  • [22] John Wilmes, Algebraic invariants of sandpile graphs, Bachelor's thesis, Reed College, 2010.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 13D02, 05C25

Retrieve articles in all journals with MSC (2010): 13D02, 05C25


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
Email: schreyer@math.uni-sb.de

John Wilmes
Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637
Email: wilmesj@math.uchicago.edu

DOI: https://doi.org/10.1090/S0002-9947-2014-06248-X
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.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society