ALGEBRAIC COMBINATORICS

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.

Revised:
Accepted:
Published online:
DOI: 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},
mrnumber = {3856526},
zbl = {06882343},
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://www.ams.org/mathscinet-getitem?mr=3856526
UR  - https://zbmath.org/?q=an%3A06882343
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

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

[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 | Zbl

[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 | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | DOI | MR | Zbl

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

Cited by Sources: