Divisors on graphs, connected flags, and syzygies. (English) Zbl 1305.05132

Mohammadi, Fatemeh; Shokrieh, Farbod

Int. Math. Res. Not. 2014, No. 24, 6839-6905 (2014).

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.

MSC:

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

Keywords:

binomial ideals; monomial ideals; minimal Gröbner bases