×

zbMATH — the first resource for mathematics

Minimal free resolutions of the \(G\)-parking function ideal and the toppling ideal. (English) Zbl 1310.13022
This paper gives an explicit minimal free resolution \(\mathcal{F}_0\) for the \(G\)-parking function ideal, \(M_G\), of any connected undirected multigraph \(G\) (which is also referred to as a weighted graph or a graph with edge weights in the literature) and an explicit minimal free resolution \(\mathcal{F}_1\) for the toppling ideal \(I_G\) of the graph. These results answer a question of A. Postnikov and B. Shapiro [Trans. Am. Math. Soc. 356, No. 8, 3109–3142 (2004; Zbl 1043.05038)] in the case of undirected multigraphs. As a consequence, the authors settle a conjecture of M. Manjunath and B. Sturmfels [J. Algebr. Comb. 37, No. 4, 737–756 (2013; Zbl 1272.13017)] by showing that \(M_G\) and \(I_G\) have the same Betti numbers. The paper also resolved a conjecture of Perkinson and Wilmes by describing how the combinatorial information of the graph is encoded in the minimal free resolutions. A running example is maintained throughout the paper, which provides a helpful concrete demonstration of many of the results.
In Section 1, the authors give an overview of the results and a nice review of relevant literature. They state Theorem 1.1, which equates the \(k^{th}\) Betti number of both \(I_G\) and \(M_G\) with the sum over all connected \(k+1\)-partitions of the number of acyclic orientations with a unique sink on the graph associated to the partition. In Section \(2\), they give relevant definitions and prove the necessary technical lemmas regarding acyclic \(k\)-partitions, chip-firing, equivalence classes, and divisors. They explain edge contractions, which provide the basis for the differentials of the free resolutions.
In Section 3, the authors define the free modules and differentials that form the resolution \(\mathcal{F}_1\) and show that it is a complex and that the cokernel of the final map is \(I_G\). In Section \(4\) they repeat the process to form \(\mathcal{F}_0\) with the appropriate cokernel being \(M_G\). They clearly explain the differences between the two resolutions, then conclude the section by showing that if \(T\) is a tree, \(\mathcal{F}_0(T)\) is isomorphic to the Koszul complex.
In Section 5, the authors prove the exactness of \(\mathcal{F}_0\) by reducing to the complexes of vector spaces. In Section \(6\) they use a Gröbner basis degeneration argument to show that \(\mathcal{F}_1\) is exact. In fact, they introduce a variable \(t\) to homogenize \(\mathcal{F}_1\) with respect to an integral weight function. They then work with the family of complexes \(\mathcal{F}_t(G)\). Using a quotient module (setting \(t=0\)) gives \(\mathcal{F}_0\) as the free resolution of \(M_G\). Also, localization at \(t\), or setting \(t=1\), yields \(\mathcal{F}_1\) as the minimal resolution of \(I_G\). It was shown by Cori, Rossin, and Salvy [R. Cori et al., Theor. Comput. Sci. 276, No. 1–2, 1–15 (2002; Zbl 1002.68105)] that \(M_G\) is an initial ideal of \(IG\). In this paper, Corollary 6.6 shows that the minimal free resolution of \(M_G\) is a Gröbner degeneration of the minimal free resolution of \(I_G\). The article concludes by showing in Section \(7\) that the complex \(\mathcal{F}_0\) is a cellular resolution, that is, it is supported on a \(CW\)-complex.

MSC:
13D02 Syzygies, resolutions, complexes and commutative rings
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05E40 Combinatorial aspects of commutative algebra
13F55 Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Software:
Macaulay2; SageMath
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Amini, Omid; Manjunath, Madhusudan, Riemann-Roch for sub-lattices of the root lattice \(A_n\), Electron. J. Combin., 17, 1, Research Paper 124, 50 pp., (2010) · Zbl 1277.05105
[2] Baker, Matthew; Norine, Serguei, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 2, 766-788, (2007) · Zbl 1124.05049
[3] Baker, Matthew; Shokrieh, Farbod, Chip-firing games, potential theory on graphs, and spanning trees, J. Combin. Theory Ser. A, 120, 1, 164-182, (2013) · Zbl 1408.05089
[4] Benson, Brian; Chakrabarty, Deeparnab; Tetali, Prasad, \(G\)-parking functions, acyclic orientations and spanning trees, Discrete Math., 310, 8, 1340-1353, (2010) · Zbl 1230.05265
[5] Cori, Robert; Rossin, Dominique; Salvy, Bruno, Polynomial ideals for sandpiles and their Gr\"obner bases, Theoret. Comput. Sci., 276, 1-2, 1-15, (2002) · Zbl 1002.68105
[6] Dhar, Deepak, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 14, 1613-1616, (1990) · Zbl 0943.82553
[7] [DocSan] Anton Dochtermann and Ramal Sanyal, Laplacian ideals, arrangements, and resolutions, J. Algebr. Comb. (2012), 1–18, DOI 10.1007/s10801-014-0508-7.
[8] Eisenbud, David, Commutative algebra, Graduate Texts in Mathematics 150, xvi+785 pp., (1995), Springer-Verlag: New York:Springer-Verlag · Zbl 0819.13001
[9] Goles, Eric; Prisner, Erich, Source reversal and chip firing on graphs, Theoret. Comput. Sci., 233, 1-2, 287-295, (2000) · Zbl 0947.05039
[10] [m2] 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] Harris, Joe, Algebraic geometry, Graduate Texts in Mathematics 133, xx+328 pp., (1995), Springer-Verlag: New York:Springer-Verlag · Zbl 0779.14001
[12] Holroyd, Alexander E.; Levine, Lionel; M\'esz\'aros, Karola; Peres, Yuval; Propp, James; Wilson, David B., Chip-firing and rotor-routing on directed graphs. In and out of equilibrium. 2, Progr. Probab. 60, 331-364, (2008), Birkh\`‘auser: Basel:Birkh\'’auser · Zbl 1173.82339
[13] Hopkins, Sam, Another proof of Wilmes’ conjecture, Discrete Math., 323, 43-48, (2014) · Zbl 1283.05215
[14] [Man12] Horia Mania, Wilmes’ conjecture and boundary divisors, arXiv:1210.8109 (2012).
[15] Manjunath, Madhusudan; Sturmfels, Bernd, Monomials, binomials and Riemann-Roch, J. Algebraic Combin., 37, 4, 737-756, (2013) · Zbl 1272.13017
[16] Miller, Ezra; Sturmfels, Bernd, Combinatorial commutative algebra, Graduate Texts in Mathematics 227, xiv+417 pp., (2005), Springer-Verlag: New York:Springer-Verlag · Zbl 1090.13001
[17] Mohammadi, Fatemeh; Shokrieh, Farbod, 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, 885-896, (2013), Assoc. Discrete Math. Theor. Comput. Sci., Nancy · Zbl 1294.05092
[18] Perkinson, David; Perlman, Jacob; Wilmes, John, Primer for the algebraic geometry of sandpiles. Tropical and non-Archimedean geometry, Contemp. Math. 605, 211-256, (2013), Amer. Math. Soc., Providence, RI · Zbl 1320.05060
[19] Postnikov, Alexander; Shapiro, Boris, Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc., 356, 8, 3109-3142 (electronic), (2004) · Zbl 1043.05038
[20] [sage] W.A. Stein et al., Sage Mathematics Software (Version 5.0), The Sage Development Team, 2012, http://www.sagemath.org.
[21] Velasco, Mauricio, Minimal free resolutions that are not supported by a CW-complex, J. Algebra, 319, 1, 102-114, (2008) · Zbl 1133.13015
[22] [Wil10] John Wilmes, Algebraic invariants of sandpile graphs, Bachelor’s thesis, Reed College, 2010. \endbiblist
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.