zbMATH — the first resource for mathematics

Divisors on graphs, connected flags, and syzygies. (English) Zbl 1305.05132
Summary: We study the binomial and monomial ideals arising from linear equivalence of divisors on graphs from the point of view of Gröbner theory. We give an explicit description of a minimal Gröbner bases for each higher syzygy module. In each case, the given minimal Gröbner bases is also a minimal generating set. The Betti numbers of the binomial ideal and its natural initial ideal coincide and they correspond to the number of “connected flags” in the graph. In particular, the Betti numbers are independent of the characteristic of the base field. For complete graphs, the problem was previously studied by A. Postnikov and B. Shapiro [Trans. Am. Math. Soc. 356, No. 8, 3109–3142 (2004; Zbl 1043.05038)] and by M. Manjunath and B. Sturmfels [J. Algebr. Comb. 37, No. 4, 737–756 (2013; Zbl 1272.13017)]. The case of a general graph was stated as an open problem.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13D02 Syzygies, resolutions, complexes and commutative rings
13P99 Computational aspects and applications of commutative rings
Full Text: DOI arXiv