An algorithm for computing the universal Gröbner Basis of graph ideals

ABSTRACT

The universal Gröbner basis of an ideal is a Gröbner basis with respect to all term orders simultaneously. The aim of this paper is to present an algorithmic approach to compute the universal Gröbner basis for the toric ideal corresponding to an undirected graph, based on the theoretical knowledge of this set and on a recent, efficiently computable algorithmic characterization of the Graver basis of the ideal.

KEYWORDS:

• Algorithms
• universal Gröbner basis
• complexity
• Graver basis
• toric ideals of graphs
• Gröbner bases

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• Primary 14M25
• 68Q40
• 68W30
• 13P10
• 05C85

Acknowledgments

The authors would like to thank the referees for their very careful reading and essential remarks on how to improve the article.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Christos Tatakis  http://orcid.org/0000-0002-0112-6313