zbMATH — the first resource for mathematics

Lexicographic and reverse lexicographic quadratic Gröbner bases of cut ideals. (English) Zbl 1457.13051
Summary: Hibi conjectured that if a toric ideal has a quadratic Gröbner basis, then the toric ideal has either a lexicographic or a reverse lexicographic quadratic Gröbner basis. In this paper, we present a cut ideal of a graph that serves as a counterexample to this conjecture. We also discuss the existence of a quadratic Gröbner basis of a cut ideal of a cycle. U. Nagel and S. Petrović [J. Commut. Algebra 1, No. 3, 547–565 (2009; Zbl 1190.13016)] claimed that a cut ideal of a cycle has a lexicographic quadratic Gröbner basis using the results of J. Chifman and S. Petrović [Lect. Notes Comput. Sci. 4545, 307–321 (2007; Zbl 1127.92030)]. However, we point out that the results of Chifman and Petrović [loc. cit.] used by Nagel and Petrović [loc. cit.] are incorrect for cycles of length greater than or equal to 6. Hence the existence of a quadratic Gröbner basis for the cut ideal of a cycle (a ring graph) is an open question. We also provide a lexicographic quadratic Gröbner basis of a cut ideal of a cycle of length less than or equal to 7.

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13A70 General commutative ring theory and combinatorics (zero-divisor graphs, annihilating-ideal graphs, etc.)
05E40 Combinatorial aspects of commutative algebra
CoCoA; Risa/Asir
Full Text: DOI
[1] Abbott, J.; Bigatti, A. M.; Robbiano, L., CoCoA: a system for doing computations in commutative algebra, Available at
[2] Aoki, S.; Hibi, T.; Ohsugi, H.; Takemura, A., Gröbner bases of nested configurations, J. Algebra, 320, 6, 2583-2593 (2008) · Zbl 1152.14047
[3] Aoki, S.; Hibi, T.; Ohsugi, H.; Takemura, A., Markov basis and Gröbner basis of Segre-Veronese configuration for testing independence in group-wise selections, Ann. Inst. Stat. Math., 62, 299-321 (2010) · Zbl 1440.62219
[4] Aramova, A.; Herzog, J.; Hibi, T., Finite lattices and lexicographic Gröbner bases, Eur. J. Comb., 21, 431-439 (2000) · Zbl 0969.13010
[5] Chifman, J.; Petrović, S., Toric ideals of phylogenetic invariants for the general group-based model on claw trees \(K_{1 , n}\), (Anai, H.; Horimoto, K.; Kutsia, T., Proceedings of the Second International Conference on Algebraic Biology. Proceedings of the Second International Conference on Algebraic Biology, Springer LNCS, vol. 4545 (2007), Springer-Verlag), 307-321 · Zbl 1127.92030
[6] D’Alì, A., Toric ideals associated with gap-free graphs, J. Pure Appl. Algebra, 219, 9, 3862-3872 (2015) · Zbl 1435.13022
[7] Deza, M.; Laurent, M., Geometry of Cuts and Metrics (1997), Springer-Verlag: Springer-Verlag Berlin · Zbl 0885.52001
[8] Engström, A., Cut ideals of \(K_4\)-minor free graphs are generated by quadratics, Mich. Math. J., 60, 3, 705-714 (2011) · Zbl 1234.14036
[9] Hibi, T.; Nishiyama, K.; Ohsugi, H.; Shikama, A., Many toric ideals generated by quadratic binomials possess no quadratic Gröbner bases, J. Algebra, 408, 138-146 (2014) · Zbl 1304.13040
[10] Nagel, U.; Petrović, S., Properties of cut ideals associated to ring graphs, J. Commut. Algebra, 1, 547-565 (2009) · Zbl 1190.13016
[11] Noro, N., Risa/Asir, a computer algebra system · Zbl 1027.68152
[12] Ohsugi, H.; Herzog, J.; Hibi, T., Combinatorial pure subrings, Osaka J. Math., 37, 745-757 (2000) · Zbl 1096.13525
[13] Ohsugi, H.; Hibi, T., Toric ideals generated by quadratic binomials, J. Algebra, 218, 509-527 (1999) · Zbl 0943.13014
[14] Ohsugi, H.; Hibi, T., Koszul bipartite graphs, Adv. Appl. Math., 22, 25-28 (1999) · Zbl 0916.05046
[15] Ohsugi, H.; Hibi, T., Compressed polytopes, initial ideals and complete multipartite graphs, Ill. J. Math., 44, 391-406 (2000) · Zbl 0943.13016
[16] Ohsugi, H.; Hibi, T., Quadratic initial ideals of root systems, Proc. Am. Math. Soc., 130, 1913-1922 (2002) · Zbl 1012.13012
[17] Ohsugi, H.; Hibi, T., Two way subtable sum problems and quadratic Gröbner bases, Proc. Am. Math. Soc., 137, 5, 1539-1542 (2009) · Zbl 1162.13012
[18] Ohsugi, H.; Hibi, T., Toric rings and ideals of nested configurations, J. Commut. Algebra, 2, 187-208 (2010) · Zbl 1237.13053
[19] Shibata, K., Strong Koszulness of the toric ring associated to a cut ideal, Comment. Math. Univ. St. Pauli, 64, 71-80 (2015) · Zbl 1330.13017
[20] Sturmfels, B., Gröbner Bases and Convex Polytopes (1996), American Mathematical Society · Zbl 0856.13020
[21] Sturmfels, B.; Sullivant, S., Toric geometry of cuts and splits, Mich. Math. J., 57, 689-709 (2008) · Zbl 1180.13040
[22] Sullivant, S., Toric fiber products, J. Algebra, 316, 560-577 (2007) · Zbl 1129.13030
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.