Minimal free resolutions of the 𝐺-parking function ideal and the toppling ideal

Manjunath, Madhusudan; Schreyer, Frank-Olaf; Wilmes, John

doi:10.1090/S0002-9947-2014-06248-X

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.