Laplacian ideals, arrangements, and resolutions.

*(English)*Zbl 1303.05217Summary: The Laplacian matrix of a graph \(G\) describes the combinatorial dynamics of the abelian sandpile model and the more general Riemann-Roch theory of \(G\). The lattice ideal associated to the lattice generated by the columns of the Laplacian provides an algebraic perspective on this recently (re)emerging field. This binomial ideal \(I_G\) has a distinguished monomial initial ideal \(M_G\), characterized by the property that the standard monomials are in bijection with the \(G\)-parking functions of the graph \(G\). The ideal \(M_G\) was also considered by A. Postnikov and B. Shapiro [Trans. Am. Math. Soc. 356, No. 8, 3109–3142 (2004; Zbl 1043.05038)] in the context of monotone monomial ideals.

We study resolutions of \(M_G\) and show that a minimal-free cellular resolution is supported on the bounded subcomplex of a section of the graphical arrangement of \(G\). This generalizes constructions from Postnikov and Shapiro (for the case of the complete graph) and connects to work of M. Manjunath and B. Sturmfels [J. Algebr. Comb. 37, No. 4, 737–756 (2013; Zbl 1272.13017)] and of D. Perkinson et al. [“Primer for the algebraic geometry of sandpiles”, Preprint, arXiv:1112.6163] on the commutative algebra of sandpiles. As a corollary, we verify a conjecture of Perkinson et al. [loc. cit.] regarding the Betti numbers of \(M_G\) and in the process provide a combinatorial characterization in terms of acyclic orientations.

We study resolutions of \(M_G\) and show that a minimal-free cellular resolution is supported on the bounded subcomplex of a section of the graphical arrangement of \(G\). This generalizes constructions from Postnikov and Shapiro (for the case of the complete graph) and connects to work of M. Manjunath and B. Sturmfels [J. Algebr. Comb. 37, No. 4, 737–756 (2013; Zbl 1272.13017)] and of D. Perkinson et al. [“Primer for the algebraic geometry of sandpiles”, Preprint, arXiv:1112.6163] on the commutative algebra of sandpiles. As a corollary, we verify a conjecture of Perkinson et al. [loc. cit.] regarding the Betti numbers of \(M_G\) and in the process provide a combinatorial characterization in terms of acyclic orientations.

##### MSC:

05E40 | Combinatorial aspects of commutative algebra |

05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

13D02 | Syzygies, resolutions, complexes and commutative rings |

52C35 | Arrangements of points, flats, hyperplanes (aspects of discrete geometry) |

##### Keywords:

graph Laplacian; chip-firing; lattice ideal; initial ideal; \(G\)-parking function; cellular resolution; graphical arrangement; acyclic orientation##### References:

[1] | Baker, M; Norine, S, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 766-788, (2007) · Zbl 1124.05049 |

[2] | Bayer, D; Popescu, S; Sturmfels, B, Syzygies of unimodular Lawrence ideals, J. Reine Angew. Math., 534, 169-186, (2001) · Zbl 1011.13006 |

[3] | Bayer, D; Sturmfels, B, Cellular resolutions of monomial modules, J. Reine Angew. Math., 502, 123-140, (1998) · Zbl 0909.13011 |

[4] | Benson, B; Chakrabarty, D; Tetali, P, \(G\)-parking functions, acyclic orientations and spanning trees, Discret. Math., 310, 1340-1353, (2010) · Zbl 1230.05265 |

[5] | Björner, A., Wachs, M. L.: Geometrically constructed bases for homology of partition lattices of type \(A\), \(B\) and \(D\), Electron. J. Combin., 11, pp. Research Paper 3, 26 (2004/06) |

[6] | Gabrielov, A, Abelian avalanches and Tutte polynomials, Physica A, 195, 253-274, (1993) |

[7] | Godsil, C; Royle, G, Algebraic graph theory, No. 207, (2001), New York · Zbl 0968.05002 |

[8] | Greene, C; Zaslavsky, T, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Am. Math. Soc., 280, 97-126, (1983) · Zbl 0539.05024 |

[9] | Hopkins, S., Perkinson, D.: Bigraphical arrangements. Trans. Am. Math. Soc. (to appear) · Zbl 1325.05089 |

[10] | Linial, N, Hard enumeration problems in geometry and combinatorics, SIAM J. Algebraic Discret. Methods, 7, 331-335, (1986) · Zbl 0596.68041 |

[11] | Manjunath, M., Schreyer, F.-O., Wilmes, J.: Minimal free resolutions of the \(G\)-parking function ideal and the toppling ideal. Trans. Am. Math. Soc. (to appear). arXiv:1210.7569 · Zbl 1310.13022 |

[12] | Manjunath, M., Sturmfels, B.: Monomials, binomials, and Riemann-Roch. J. Algebr. Comb. 37, 737-756 (2013) · Zbl 1272.13017 |

[13] | Miller, E; Sturmfels, B, Combinatorial commutative algebra, No. 227, (2005), New York · Zbl 1090.13001 |

[14] | Mohammadi, F., Shokrieh, F.: Divisors on graphs, connected flags, and syzygies. Internat. Math. Res. Notices (to appear). arXiv:1210.6622 · Zbl 1294.05092 |

[15] | Peeva, I; Sturmfels, B, Generic lattice ideals, J. Am. Math. Soc., 11, 363-373, (1998) · Zbl 0905.13005 |

[16] | Perkinson, D., Perlman, J., Wilmes, J.: Primer for the algebraic geometry of sandpiles. In: Tropical and Non-Archimedean Geometry, Contemporary Mathematics, vol. 605. American Mathematical Society, Providence, RI (2013). arXiv:1112.6163 · Zbl 1320.05060 |

[17] | Postnikov, A; Shapiro, B, Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Am. Math. Soc., 356, 3109-3142, (2004) · Zbl 1043.05038 |

[18] | Stanley, R.P.: Hyperplane arrangements, parking functions and tree inversions, in Mathematical essays in honor of Gian-Carlo Rota (Cambridge, MA, 1996), vol. 161 of Progr. Math., Birkhäuser Boston, Boston, MA, pp. 359-375 (1998) |

[19] | Stanley, R.P.: An introduction to hyperplane arrangements. In: Geometric Combinatorics, IAS/Park City Mathematics Series, vol. 13. American Mathematical Society, Providence, RI, pp. 389-496 (2007) · Zbl 1136.52009 |

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.