Minimal free resolutions of lattice ideals of digraphs
Algebraic Combinatorics, Volume 1 (2018) no. 2, pp. 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:
Revised:
Accepted:
Published online:
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
O’Carroll, Liam 1; Planas-Vilanova, Francesc 2

1. School of Mathematics University of Edinburgh James Clerk Maxwell Building Peter Guthrie Tait Road Edinburgh EH9 3FD Scotland.
2. Departament de Matemàtiques ETSEIB, Universitat Politècnica de Catalunya Diagonal 647, ETSEIB, 08028 Barcelona Catalunya.
@article{ALCO_2018__1_2_283_0,
     author = {O{\textquoteright}Carroll, Liam and Planas-Vilanova, Francesc},
     title = {Minimal free resolutions of lattice ideals of digraphs},
     journal = {Algebraic Combinatorics},
     pages = {283--326},
     publisher = {MathOA foundation},
     volume = {1},
     number = {2},
     year = {2018},
     doi = {10.5802/alco.15},
     zbl = {06882343},
     mrnumber = {3856526},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.15/}
}
TY  - JOUR
AU  - O’Carroll, Liam
AU  - Planas-Vilanova, Francesc
TI  - Minimal free resolutions of lattice ideals of digraphs
JO  - Algebraic Combinatorics
PY  - 2018
DA  - 2018///
SP  - 283
EP  - 326
VL  - 1
IS  - 2
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.15/
UR  - https://zbmath.org/?q=an%3A06882343
UR  - https://www.ams.org/mathscinet-getitem?mr=3856526
UR  - https://doi.org/10.5802/alco.15
DO  - 10.5802/alco.15
LA  - en
ID  - ALCO_2018__1_2_283_0
ER  - 
%0 Journal Article
%A O’Carroll, Liam
%A Planas-Vilanova, Francesc
%T Minimal free resolutions of lattice ideals of digraphs
%J Algebraic Combinatorics
%D 2018
%P 283-326
%V 1
%N 2
%I MathOA foundation
%U https://doi.org/10.5802/alco.15
%R 10.5802/alco.15
%G en
%F 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, pp. 283-326. doi : 10.5802/alco.15. https://alco.centre-mersenne.org/articles/10.5802/alco.15/

[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, Encyclopedia of Mathematics and its Applications, 39, Cambridge University Press, Cambridge, 1991, x+367 pages | Article | MR 1130611 | Zbl 0746.05002

[6] Bruns, Winfried; Herzog, Jürgen Cohen–Macaulay rings, Cambridge Studies in Advanced Mathematics, 39, Cambridge University Press, Cambridge, 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, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 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, Graduate Texts in Mathematics, 150, Springer-Verlag, New York, 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, Translated by K. A. Hirsch, Chelsea Publishing Co., New York, 1959, Vol. 1, x+374 pp. Vol. 2, ix+276 pages | MR 0107649 | Zbl 0927.15002

[14] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 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 (Contemp. Math.), Volume 605, Amer. Math. Soc., Providence, RI, 2013, pp. 211-256 | Article | MR 3204273 | Zbl 1320.05060

Cited by Sources: