Minimal free resolutions of lattice ideals of digraphs
Algebraic Combinatorics, Volume 1 (2018) no. 2, p. 283-326
Based upon a previous work of Manjunath and Sturmfels for a finite, complete, undirected graph, and a refined algorithm by Eröcal, Motsak, Schreyer and Steenpaß for computing syzygies, we display a free resolution of the lattice ideal associated to a finite, strongly connected, weighted, directed graph. Moreover, the resolution is minimal precisely when the digraph is strongly complete.
Received : 2017-11-17
Revised : 2018-02-07
Accepted : 2018-02-08
Published online : 2018-03-02
DOI : https://doi.org/10.5802/alco.15
Classification:  13D02,  13P10,  05C25,  05C50,  05EXX
Keywords: Directed graph, lattice ideal, Gröbner basis, minimal free resolution
@article{ALCO_2018__1_2_283_0,
     author = {O{'}Carroll, Liam and Planas-Vilanova, Francesc},
     title = {Minimal free resolutions of lattice ideals of digraphs},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {1},
     number = {2},
     year = {2018},
     pages = {283-326},
     doi = {10.5802/alco.15},
     zbl = {06882343},
     language = {en},
     url = {http://alco.centre-mersenne.org/item/ALCO_2018__1_2_283_0}
}
O’Carroll, Liam;Planas-Vilanova, Francesc. Minimal free resolutions of lattice ideals of digraphs. Algebraic Combinatorics, Volume 1 (2018) no. 2, p. 283-326. doi : 10.5802/alco.15. https://alco.centre-mersenne.org/item/ALCO_2018__1_2_283_0/

[1] Asadi, Arash; Backman, Spencer Chip-firing and Riemann–Roch Theory for Directed Graphs (2010) (https://arxiv.org/abs/1012.0287) | Zbl 1274.05189

[2] Backman, Spencer; Manjunath, Madhusudan Explicit deformation of lattice ideals via chip-firing games on directed graphs, J. Algebraic Combin., Volume 42 (2015) no. 4, pp. 1097-1110 | Article | MR 3417260 | Zbl 1328.05119

[3] Bak, Per; Tang, Chao; Wiesenfeld, Kurt Self-organized criticality, Phys. Rev. A (3), Volume 38 (1988) no. 1, pp. 364-374 | Article | MR 949160 | Zbl 1230.37103

[4] Berkesch, Christine; Schreyer, Frank-Olaf Syzygies, finite length modules, and random curves (2014) (https://arxiv.org/abs/1403.0581) | MR 3525467 | Zbl 1359.13029

[5] Brualdi, Richard A.; Ryser, Herbert J. Combinatorial matrix theory, Cambridge University Press, Cambridge, Encyclopedia of Mathematics and its Applications, Volume 39 (1991), x+367 pages | Article | MR 1130611 | Zbl 0746.05002

[6] Bruns, Winfried; Herzog, Jürgen Cohen–Macaulay rings, Cambridge University Press, Cambridge, Cambridge Studies in Advanced Mathematics, Volume 39 (1993), xii+403 pages | MR 1251956 | Zbl 0788.13005

[7] Cori, Robert; Rossin, Dominique; Salvy, Bruno Polynomial ideals for sandpiles and their Gröbner bases, Theoret. Comput. Sci., Volume 276 (2002) no. 1-2, pp. 1-15 | Article | MR 1896344 | Zbl 1002.68105

[8] Corrales, Hugo; Valencia, Carlos E. Arithmetical structures on graphs (2017) (https://arxiv.org/abs/1604.02502) | Zbl 06799758

[9] Cox, David; Little, John; O’Shea, Donal Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra, Springer-Verlag, New York, Undergraduate Texts in Mathematics (1997), xiv+536 pages | MR 1417938 | Zbl 0756.13017

[10] Decker, Wolfram; Schreyer, Frank-Olaf Varieties, Gröbner Bases and Algebraic Curves (2011) (http://www.mathematik.uni-kl.de/~decker/Lehre/SS12/AlgebraicGeometry/material/BookDeckerSchreyer_v2.pdf)

[11] Eisenbud, David Commutative algebra. With a view toward algebraic geometry, Springer-Verlag, New York, Graduate Texts in Mathematics, Volume 150 (1995), xvi+785 pages | MR 1322960 | Zbl 0819.13001

[12] Eröcal, Burçin; Motsak, Oleksandr; Schreyer, Frank-Olaf; Steenpaß, Andreas Refined algorithms to compute syzygies, J. Symbolic Comput., Volume 74 (2016), pp. 308-327 | Article | MR 3424044 | Zbl 06517845

[13] Gantmacher, F. R. The theory of matrices. Vols. 1, 2, Chelsea Publishing Co., New York, Translated by K. A. Hirsch (1959), Vol. 1, x+374 pp. Vol. 2, ix+276 pages | MR 0107649 | Zbl 0927.15002

[14] Godsil, Chris; Royle, Gordon Algebraic graph theory, Springer-Verlag, New York, Graduate Texts in Mathematics, Volume 207 (2001), xx+439 pages | Article | MR 1829620 | Zbl 0968.05002

[15] Greuel, Gert-Martin; Pfister, Gerhard A Singular introduction to commutative algebra, Springer, Berlin (2008), xx+689 pages (With contributions by Olaf Bachmann, Christoph Lossen and Hans Schönemann) | MR 2363237 | Zbl 1133.13001

[16] Loughry, J.; Van Hemert, J.I.; Schoofs, L. Efficiently Enumerating the Subsets of a Set (2000) (http://www.applied-math.org/subset.pdf)

[17] Manjunath, Madhusudan; Schreyer, Frank-Olaf; Wilmes, John Minimal free resolutions of the G-parking function ideal and the toppling ideal, Trans. Amer. Math. Soc., Volume 367 (2015) no. 4, pp. 2853-2874 | Article | MR 3301884 | Zbl 1310.13022

[18] Manjunath, Madhusudan; Sturmfels, Bernd Monomials, binomials and Riemann–Roch, J. Algebraic Combin., Volume 37 (2013) no. 4, pp. 737-756 | Article | MR 3047017 | Zbl 1272.13017

[19] Mohammadi, Fatemeh; Shokrieh, Farbod Divisors on graphs, connected flags, and syzygies, Int. Math. Res. Not. (2014) no. 24, pp. 6839-6905 | Article | MR 3291642 | Zbl 1305.05132

[20] O’Carroll, Liam; Planas-Vilanova, Francesc The primary components of positive critical binomial ideals, J. Algebra, Volume 373 (2013), pp. 392-413 | Article | MR 2995033 | Zbl 1274.13002

[21] O’Carroll, Liam; Planas-Vilanova, Francesc; Villarreal, Rafael H. Degree and algebraic properties of lattice and matrix ideals, SIAM J. Discrete Math., Volume 28 (2014) no. 1, pp. 394-427 | Article | MR 3180844 | Zbl 1334.13017

[22] Perkinson, David; Perlman, Jacob; Wilmes, John Primer for the algebraic geometry of sandpiles, Tropical and non-Archimedean geometry, Amer. Math. Soc., Providence, RI (Contemp. Math.) Volume 605 (2013), pp. 211-256 | Article | MR 3204273 | Zbl 1320.05060