Skip to main content
SpringerLink
Log in

Divisors on graphs, binomial and monomial ideals, and cellular resolutions

  • Published:
Mathematische Zeitschrift Aims and scope Submit manuscript

Abstract

We study various binomial and monomial ideals arising in the theory of divisors, orientations, and matroids on graphs. We use ideas from potential theory on graphs and from the theory of Delaunay decompositions for lattices to describe their minimal polyhedral cellular free resolutions. We show that the resolutions of all these ideals are closely related and that their \({\mathbb {Z}}\)-graded Betti tables coincide. As corollaries, we give conceptual proofs of conjectures and questions posed by Postnikov and Shapiro, by Manjunath and Sturmfels, and by Perkinson, Perlman, and Wilmes. Various other results related to the theory of chip-firing games on graphs also follow from our general techniques and results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Notes

  1. A perfect pairing is sometimes called a unimodular pairing in the literature. We will avoid this terminology to avoid confusion.

  2. It is an elementary fact that any acyclic orientation of G has at least one source and one sink.

References

  1. An, Y., Baker, M., Kuperberg, G., Shokrieh, F.: Canonical representatives for divisor classes on tropical curves and the matrix-tree theorem. Forum Math. Sigma 2, e24–25 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bacher, R., de la Harpe, P., Nagnibeda, T.: The lattice of integral flows and the lattice of integral cuts on a finite graph. Bull. Soc. Math. Fr. 125(2), 167–198 (1997)

    MathSciNet  MATH  Google Scholar 

  3. Baker, M., Faber, X.: Metrized graphs, Laplacian operators, and electrical networks. In: Quantum Graphs and Their Applications, pp. 15–33 (2006)

  4. Bruns, W., Herzog, J.: Cohen–Macaulay Rings, Cambridge Studies in Advanced Mathematics, vol. 39. Cambridge University Press, Cambridge (1993)

    MATH  Google Scholar 

  5. Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge Mathematical Library, Cambridge University Press, Cambridge (1993)

    MATH  Google Scholar 

  6. Biggs, N.: Algebraic potential theory on graphs. Bull. Lond. Math. Soc. 29(6), 641–682 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  7. Biggs, N.: Chip-firing and the critical group of a graph. J. Algebraic Comb. 9(1), 25–45 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  8. Björner, A.: The homology and shellability of matroids and geometric lattices. In: Matroid Applications. Encyclopedia of Mathematics and its Applications, vol. 40. Cambridge University Press, Cambridge, pp. 226–283 (1992)

  9. Björner, A., Lovász, L., Shor, P.W.: Chip-firing games on graphs. Eur. J. Comb. 12(4), 283–291 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  10. Björner, A., Vergnas, M.L., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids, Second, Encyclopedia of Mathematics and Its Applications, vol. 46. Cambridge University Press, Cambridge (1999)

    Google Scholar 

  11. Baker, M., Norine, S.: Riemann–Roch and Abel–Jacobi theory on a finite graph. Adv. Math. 215(2), 766–788 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  12. Boocher, A.: Free resolutions and sparse determinantal ideals. Math. Res. Lett. 19(4), 805–821 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  13. Bayer, D., Popescu, S., Sturmfels, B.: Syzygies of unimodular Lawrence ideals. J. Reine Angew. Math. 534, 169–186 (2001)

    MathSciNet  MATH  Google Scholar 

  14. Baker, M., Shokrieh, F.: Chip-firing games, potential theory on graphs, and spanning trees. J. Comb. Theory Ser. A 120(1), 164–182 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Bayer, D., Sturmfels, B.: Cellular resolutions of monomial modules. J. Reine Angew. Math. 502, 123–140 (1998)

    MathSciNet  MATH  Google Scholar 

  16. Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality. Phys. Rev. A (3) 38(1), 364–374 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  17. Batzies, E., Welker, V.: Discrete Morse theory for cellular resolutions. J. Reine Angew. Math. 543, 147–168 (2002)

    MathSciNet  MATH  Google Scholar 

  18. Conca, A., Hoşten, S., Thomas, R.R.: Nice initial complexes of some classical ideals. In: Algebraic and Geometric Combinatorics, pp. 11–42 (2006)

  19. Cori, R., Le Borgne, Y.: The sand-pile model and Tutte polynomials. Adv. Appl. Math. 30(1–2), 44–52 (2003). Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001)

    Article  MathSciNet  MATH  Google Scholar 

  20. Chinburg, T., Rumely, R.: The capacity pairing. J. Reine Angew. Math. 434, 1–44 (1993)

    MathSciNet  MATH  Google Scholar 

  21. Cori, R., Rossin, D., Salvy, B.: Polynomial ideals for sandpiles and their Gröbner bases. Theoret. Comput. Sci. 276(1–2), 1–15 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  22. Conway, J.H., Sloane, N.J.A.: Sphere packings, lattices and groups, Third, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290. Springer, New York (1999). With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov

  23. Dhar, D.: Self-organized critical state of sandpile automaton models. Phys. Rev. Lett. 64(14), 1613–1616 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  24. De Loera, J.A., Rambau, J., Santos, F.: Triangulations, Algorithms and Computation in Mathematics, vol. 25. Springer, Berlin (2010). Structures for algorithms and applications

    MATH  Google Scholar 

  25. Dochtermann, A., Mohammadi, F.: Cellular resolutions from mapping cones. J. Comb. Theory Ser. A 128, 180–206 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  26. Dochtermann, A., Sanyal, R.: Laplacian ideals, arrangements, and resolutions. J. Algebraic Comb. 40(3), 805–822 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  27. Eisenbud, D.: The Geometry of Syzygies, Graduate Texts in Mathematics, vol. 229. Springer, New York (2005). A second course in commutative algebra and algebraic geometry

    Google Scholar 

  28. Eisenbud, D.: Commutative Algebra, Graduate Texts in Mathematics, vol. 150. Springer, New York (1995). With a view toward algebraic geometry

    Google Scholar 

  29. Engström, A.: Complexes of directed trees and independence complexes. Discrete Math. 309(10), 3299–3309 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  30. Erdahl, R.M., Ryshkov, S.S.: On lattice dicing. European J. Combin. 15(5), 459–481 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  31. Gabrielov, A.: Abelian avalanches and Tutte polynomials. Phys. A 195(1–2), 253–274 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  32. Gathmann, A., Kerber, M.: A Riemann–Roch theorem in tropical geometry. Math. Z. 259(1), 217–230 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  33. Greuel, G.-M., Pfister, G.: A Singular Introduction to Commutative Algebra, Extended edition. Springer, Berlin (2008). With contributions by Olaf Bachmann, Christoph Lossen and Hans Schönemann

  34. 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(1), 97–126 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  35. Herzog, J., Hibi, T.: Monomial Ideals, Graduate Texts in Mathematics, vol. 260. Springer, London (2011)

    Book  MATH  Google Scholar 

  36. Hopkins, S.: Another proof of Wilmes’ conjecture. Discrete Math. 323, 43–48 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  37. Hopkins, S., Perkinson, D.: Orientations, semiorders, arrangements, and parking functions. Electron. J. Combin 19(4), 8–31 (2012)

    MathSciNet  MATH  Google Scholar 

  38. Jojić, D.: Shellability of complexes of directed trees. Filomat 27(8), 1551–1559 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  39. Kind, B., Kleinschmidt, P.: Schälbare Cohen-Macauley-Komplexe und ihre Parametrisierung. Math. Z. 167(2), 173–179 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  40. Kateri, M., Mohammadi, F., Sturmfels, B.: A family of quasisymmetry models. J. Algebraic Stat. 6(1), 1–16 (2015)

    Article  MathSciNet  Google Scholar 

  41. Kozlov, D.N.: Complexes of directed trees. J. Comb. Theory Ser. A 88(1), 112–122 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  42. Lorenzini, D.J.: Arithmetical graphs. Math. Ann. 285(3), 481–501 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  43. Levine, L., Propp, J.: What is..a sandpile? Notices Am. Math. Soc. 57(8), 976–979 (2010)

    MathSciNet  MATH  Google Scholar 

  44. Mania, H.: Wilmes’ conjecture and boundary divisors (2012). Preprint arXiv:1210.8109

  45. Massey, W.S.: A Basic Course in Algebraic Topology, Graduate Texts in Mathematics, vol. 127. Springer, New York (1991)

    Google Scholar 

  46. López, C.M.: Chip firing and the Tutte polynomial. Ann. Comb. 1(3), 253–259 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  47. Mohammadi, F.: Prime splittings of determinantal ideals (2012). Preprint arXiv:1208.2930

  48. Mohammadi, F.: Divisors on graphs, orientations, syzygies, and system reliability. J. Algebraic Comb., 1–19 (2015). doi:10.1007/s10801-015-0641-y

  49. Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra, Graduate Texts in Mathematics, vol. 227. Springer, New York (2005)

    Google Scholar 

  50. Manjunath, M., Sturmfels, B.: Monomials, binomials and Riemann–Roch. J. Algebraic Comb. 37(4), 737–756 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  51. Mohammadi, F., Shokrieh, F.: Divisors on graphs, connected flags, and syzygies. Int. Math. Res. Not. IMRN 24, 6839–6905 (2014)

    MathSciNet  MATH  Google Scholar 

  52. Mohammadi, F., Cabezón, E.S., Wynn, H.P.: The algebraic method in tree percolation. arXiv preprint arXiv:1510.04036 (2015)

  53. Mohammadi, F., Cabezón, E.S., Wynn, H.P.: Types of signature analysis in reliability based on hilbert series. arXiv preprint arXiv:1510.04427 (2015)

  54. Manjunath, M., Schreyer, F.-O., Wilmes, J.: Minimal free resolutions of the \(G\)-parking function ideal and the toppling ideal. Trans. Am. Math. Soc. 367(4), 2853–2874 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  55. Mikhalkin, G., Zharkov, I.: Tropical curves, their Jacobians and theta functions. In: Curves and Abelian Varieties. Contemporary Mathematics, vol. 465. American Mathematical Society, Providence, pp. 203–230 (2008)

  56. Novik, I., Postnikov, A., Sturmfels, B.: Syzygies of oriented matroids. Duke Math. J. 111(2), 287–317 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  57. O’Carroll, L., Planas-Vilanova, F., Villarreal, R.H.: Degree and algebraic properties of lattice and matrix ideals. SIAM J. Discrete Math. 28(1), 394–427 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  58. Oda, T., Seshadri, C.S.: Compactifications of the generalized Jacobian variety. Trans. Am. Math. Soc. 253, 1–90 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  59. 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, pp. 211–256 (2013)

  60. Postnikov, A., Shapiro, B.: Trees, parking functions, syzygies, and deformations of monomial ideals. Trans. Am. Math. Soc. 356(8), 3109–3142 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  61. Raynaud, M.: Spécialisation du foncteur de Picard. Inst. Hautes Études Sci. Publ. Math. 38, 27–76 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  62. Shokrieh, F.: The monodromy pairing and discrete logarithm on the Jacobian of finite graphs. J. Math. Cryptol. 4(1), 43–56 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  63. Stanley, R.P.: Cohen–Macaulay complexes. In: Higher Combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), (1977), pp. 51–62. NATO Adv. Study Inst. Ser. C Math. Phys. Sci. 31

  64. Stanley, R.P.: Combinatorics and Commutative Algebra, Second edition, Progress in Mathematics, vol. 41. Birkhäuser Boston Inc., Boston (1996)

    Google Scholar 

  65. Sturmfels, B.: Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8. American Mathematical Society, Providence (1996)

    MATH  Google Scholar 

  66. Tutte, W.T.: Introduction to the Theory of Matroids, Modern Analytic and Computational Methods in Science and Mathematics, No. 37. American Elsevier Publishing Co., Inc., New York (1971)

    Google Scholar 

  67. Van Le, D., Mohammadi, F.: On the Orlik–Terao ideal and the relation space of a hyperplane arrangement. Adv. Appl. Math. 71, 34–51 (2015)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The first author is grateful to Volkmar Welker for his support and many helpful conversations during this project. She is also grateful to Jürgen Herzog for helpful discussions related to regular sequences and flat families. The second author would like to thank his advisor Matthew Baker for his support throughout this project and for many useful conversations. We would like to thank Bernd Sturmfels for useful discussions. We would like to thank Winfried Bruns for valuable comments on an earlier draft of this paper. We also thank the anonymous referee for valuable suggestions.

Author information

Authors and Affiliations

  1. Institut für Mathematik, Technische Universität Berlin, 10623, Berlin, Germany

    Fatemeh Mohammadi

  2. Cornell University, Ithaca, NY, 14853-4201, USA

    Farbod Shokrieh

Authors
  1. Fatemeh Mohammadi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Farbod Shokrieh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Farbod Shokrieh.

Additional information

Fatemeh Mohammadi was supported by the Alexander von Humboldt Foundation. Farbod Shokrieh was partially supported by NSF Grant DMS-1201473.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mohammadi, F., Shokrieh, F. Divisors on graphs, binomial and monomial ideals, and cellular resolutions. Math. Z. 283, 59–102 (2016). https://doi.org/10.1007/s00209-015-1589-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00209-015-1589-2

Keywords

Search

Navigation