×

zbMATH — the first resource for mathematics

Divisors on graphs, binomial and monomial ideals, and cellular resolutions. (English) Zbl 1336.05060
Summary: 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 A. Postnikov and B. Shapiro [Trans. Am. Math. Soc. 356, No. 8, 3109–3142 (2004; Zbl 1043.05038)], M. Manjunath and B. Sturmfels [J. Algebr. Comb. 37, No. 4, 737–756 (2013; Zbl 1272.13017)], and by D. Perkinson et al. [Contemporary Mathematics 605. Centre de Recherches Mathématiques Proceedings, 211–256 (2013; Zbl 1320.05060)]. Various other results related to the theory of chip-firing games on graphs also follow from our general techniques and results.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05B35 Combinatorial aspects of matroids and geometric lattices
Software:
SINGULAR
PDF BibTeX XML Cite
Full Text: DOI arXiv
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) · Zbl 1306.05013
[2] Bacher, R; Harpe, P; Nagnibeda, T, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. Fr., 125, 167-198, (1997) · Zbl 0891.05062
[3] Baker, M., Faber, X.: Metrized graphs, Laplacian operators, and electrical networks. In: Quantum Graphs and Their Applications, pp. 15-33 (2006) · Zbl 1114.94025
[4] Bruns, W., Herzog, J.: Cohen-Macaulay Rings, Cambridge Studies in Advanced Mathematics, vol. 39. Cambridge University Press, Cambridge (1993) · Zbl 0788.13005
[5] Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge Mathematical Library, Cambridge University Press, Cambridge (1993) · Zbl 0284.05101
[6] Biggs, N, Algebraic potential theory on graphs, Bull. Lond. Math. Soc., 29, 641-682, (1997) · Zbl 0892.05033
[7] Biggs, N, Chip-firing and the critical group of a graph, J. Algebraic Comb., 9, 25-45, (1999) · Zbl 0919.05027
[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, PW, Chip-firing games on graphs, Eur. J. Comb., 12, 283-291, (1991) · Zbl 0729.05048
[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)
[11] Baker, M; Norine, S, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 766-788, (2007) · Zbl 1124.05049
[12] Boocher, A, Free resolutions and sparse determinantal ideals, Math. Res. Lett., 19, 805-821, (2012) · Zbl 1273.14097
[13] Bayer, D; Popescu, S; Sturmfels, B, Syzygies of unimodular Lawrence ideals, J. Reine Angew. Math., 534, 169-186, (2001) · Zbl 1011.13006
[14] Baker, M; Shokrieh, F, Chip-firing games, potential theory on graphs, and spanning trees, J. Comb. Theory Ser. A, 120, 164-182, (2013) · Zbl 1408.05089
[15] Bayer, D; Sturmfels, B, Cellular resolutions of monomial modules, J. Reine Angew. Math., 502, 123-140, (1998) · Zbl 0909.13011
[16] Bak, P; Tang, C; Wiesenfeld, K, Self-organized criticality, Phys. Rev. A (3), 38, 364-374, (1988) · Zbl 1230.37103
[17] Batzies, E; Welker, V, Discrete Morse theory for cellular resolutions, J. Reine Angew. Math., 543, 147-168, (2002) · Zbl 1055.13012
[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) · Zbl 1116.13015
[19] Cori, R; Borgne, Y, The sand-pile model and Tutte polynomials, Adv. Appl. Math., 30, 44-52, (2003) · Zbl 1030.05058
[20] Chinburg, T; Rumely, R, The capacity pairing, J. Reine Angew. Math., 434, 1-44, (1993) · Zbl 0756.14013
[21] Cori, R; Rossin, D; Salvy, B, Polynomial ideals for sandpiles and their Gröbner bases, Theoret. Comput. Sci., 276, 1-15, (2002) · Zbl 1002.68105
[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 · Zbl 1187.14066
[23] Dhar, D, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 1613-1616, (1990) · Zbl 0943.82553
[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 · Zbl 1207.52002
[25] Dochtermann, A; Mohammadi, F, Cellular resolutions from mapping cones, J. Comb. Theory Ser. A, 128, 180-206, (2014) · Zbl 1301.05379
[26] Dochtermann, A; Sanyal, R, Laplacian ideals, arrangements, and resolutions, J. Algebraic Comb., 40, 805-822, (2014) · Zbl 1303.05217
[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 · Zbl 1066.14001
[28] Eisenbud, D.: Commutative Algebra, Graduate Texts in Mathematics, vol. 150. Springer, New York (1995). With a view toward algebraic geometry · Zbl 0819.13001
[29] Engström, A, Complexes of directed trees and independence complexes, Discrete Math., 309, 3299-3309, (2009) · Zbl 1226.05084
[30] Erdahl, RM; Ryshkov, SS, On lattice dicing, European J. Combin., 15, 459-481, (1994) · Zbl 0809.52019
[31] Gabrielov, A, Abelian avalanches and Tutte polynomials, Phys. A, 195, 253-274, (1993) · Zbl 0786.60124
[32] Gathmann, A; Kerber, M, A Riemann-Roch theorem in tropical geometry, Math. Z., 259, 217-230, (2008) · Zbl 1187.14066
[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 · Zbl 1344.13002
[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, 97-126, (1983) · Zbl 0539.05024
[35] Herzog, J., Hibi, T.: Monomial Ideals, Graduate Texts in Mathematics, vol. 260. Springer, London (2011) · Zbl 1206.13001
[36] Hopkins, S, Another proof of wilmes’ conjecture, Discrete Math., 323, 43-48, (2014) · Zbl 1283.05215
[37] Hopkins, S; Perkinson, D, Orientations, semiorders, arrangements, and parking functions, Electron. J. Combin, 19, 8-31, (2012) · Zbl 1267.05138
[38] Jojić, D, Shellability of complexes of directed trees, Filomat, 27, 1551-1559, (2013) · Zbl 1340.52022
[39] Kind, B; Kleinschmidt, P, Schälbare Cohen-macauley-komplexe und ihre parametrisierung, Math. Z., 167, 173-179, (1979) · Zbl 0388.13015
[40] Kateri, M; Mohammadi, F; Sturmfels, B, A family of quasisymmetry models, J. Algebraic Stat., 6, 1-16, (2015) · Zbl 1344.05155
[41] Kozlov, DN, Complexes of directed trees, J. Comb. Theory Ser. A, 88, 112-122, (1999) · Zbl 0934.05041
[42] Lorenzini, DJ, Arithmetical graphs, Math. Ann., 285, 481-501, (1989) · Zbl 0662.14008
[43] Levine, L; Propp, J, What is ...a sandpile?, Notices Am. Math. Soc., 57, 976-979, (2010) · Zbl 1203.82061
[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) · Zbl 0725.55001
[46] López, CM, Chip firing and the Tutte polynomial, Ann. Comb., 1, 253-259, (1997) · Zbl 0901.05004
[47] Mohammadi, F.: Prime splittings of determinantal ideals (2012). Preprint arXiv:1208.2930 · Zbl 1306.05013
[48] Mohammadi, F.: Divisors on graphs, orientations, syzygies, and system reliability. J. Algebraic Comb., 1-19 (2015). doi:10.1007/s10801-015-0641-y · Zbl 0891.05062
[49] Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra, Graduate Texts in Mathematics, vol. 227. Springer, New York (2005)
[50] Manjunath, M; Sturmfels, B, Monomials, binomials and Riemann-Roch, J. Algebraic Comb., 37, 737-756, (2013) · Zbl 1272.13017
[51] Mohammadi, F; Shokrieh, F, Divisors on graphs, connected flags, and syzygies, Int. Math. Res. Not. IMRN, 24, 6839-6905, (2014) · Zbl 1305.05132
[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) · Zbl 1405.13026
[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, 2853-2874, (2015) · Zbl 1310.13022
[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) · Zbl 1152.14028
[56] Novik, I; Postnikov, A; Sturmfels, B, Syzygies of oriented matroids, Duke Math. J., 111, 287-317, (2002) · Zbl 1022.13002
[57] O’Carroll, L; Planas-Vilanova, F; Villarreal, RH, Degree and algebraic properties of lattice and matrix ideals, SIAM J. Discrete Math., 28, 394-427, (2014) · Zbl 1334.13017
[58] Oda, T; Seshadri, CS, Compactifications of the generalized Jacobian variety, Trans. Am. Math. Soc., 253, 1-90, (1979) · Zbl 0418.14019
[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) · Zbl 1320.05060
[60] Postnikov, A; Shapiro, B, Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Am. Math. Soc., 356, 3109-3142, (2004) · Zbl 1043.05038
[61] Raynaud, M, Spécialisation du foncteur de Picard, Inst. Hautes Études Sci. Publ. Math., 38, 27-76, (1970) · Zbl 0207.51602
[62] Shokrieh, F, The monodromy pairing and discrete logarithm on the Jacobian of finite graphs, J. Math. Cryptol., 4, 43-56, (2010) · Zbl 1231.05173
[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 · Zbl 0756.14013
[64] Stanley, R.P.: Combinatorics and Commutative Algebra, Second edition, Progress in Mathematics, vol. 41. Birkhäuser Boston Inc., Boston (1996) · Zbl 0838.13008
[65] Sturmfels, B.: Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8. American Mathematical Society, Providence (1996) · Zbl 0856.13020
[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)
[67] Le, D; Mohammadi, F, On the orlik-terao ideal and the relation space of a hyperplane arrangement, Adv. Appl. Math., 71, 34-51, (2015) · Zbl 1326.52023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.