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
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},
     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., 42 (2015) no. 4, p. 1097 -1110 MR 3417260 | Zbl 1328.05119 | Article

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

[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, 39 (1991) MR 1130611 | Zbl 0746.05002 | Article

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

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

[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) 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, 150 (1995) 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., 74 (2016), p. 308 -327 MR 3424044 | Zbl 06517845 | Article

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

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

[15] Greuel, Gert-Martin; Pfister, Gerhard A Singular introduction to commutative algebra, Springer, Berlin (2008) (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., 367 (2015) no. 4, p. 2853 -2874 MR 3301884 | Zbl 1310.13022 | Article

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

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

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

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

[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.) 605 (2013), p. 211 -256 MR 3204273 | Zbl 1320.05060 | Article