Gröbner Bases

What is Gröbner basis?

In 1960s, Gröbner basis has been introduced:

• for polynomial ring: Buchberger introduced Gröbner basis to compute the structure of ideals and modules of polynomial ring.
• for power series ring: Hironaka introduced "standard basis" (similar to Gröbner basis) in his paper about the resolution of simgularities.

Recently, Gröbner basis provides the foundation for many algorithms in algebraic geometry and commutative algebra, and is put in many computer algebra systems.

Applications of Gröbner basis

Recently, applications of Gröbner basis for ideals for various fields have been studied. For examples:

• Integer programmings
• System of linear equations
• Coding theory
• Computer graphics
• Triangulations of polytopes
• Enumeration and sampling of contingency tables in computational statistics
• Symmetric bifurcation theory and orbit space reduction in physics

and so on. The aim of our research is to study the algebraic approach for the algorithms for many fields using Gröbner basis.

Our results

(Publications)

We have analyzed the structure of Gröbner bases for "toric ideals of graphs" which corresponds the linear space of cycles of graphs. Gröbner bases of undirected graphs have been studied and applied to many fields. On the other hand, Gröbner bases of directed graphs are not well understood since they have bad algebraic properties. We have studied the structure of Gröbner bases of directed graphs which have no directed cycle, and analyzed the complexities such as the degree and the number of elements in the bases. In addition, we applied these results to the following fields:

Minimum cost flow problems

We applied to the minimum cost flow problems and analyzed the complexity. Although the polynomial time algorithms are already known for the minimum cost flow, we approached from the viewpoint of algebra using Gröbner bases.

Computation of the dimension of solutions of a certain hypergeometric systems

For a certain system of linear partial differential equations (which is called "hypergeometric systems") arose from Lie algebra, we have shown that the dimension of the system can be computed using Gröbner bases. Although the dimension of these system have been already studied by Gelfand, Graev and Postnikov, we have given another proof from the algebraic viewpoint.