Gröbner Basis Techniques in Algebraic Combinatorics
(Summary)
Takayuki Hibi
Lecture 1:
A quick introduction to Gröbner bases
A Gröbner basis is a special kind of a system of
generators of an ideal of the polynomial ring.
In the talk, first of all, based on Dickson's lemma,
we introduce initial ideals and Gröbner bases.
After discussing the division algorithm with a few examples,
we turn to the Buchberger criterion, which supplies
an algorithm to compute a Gröbner basis starting from
a system of generators of an ideal. No special knowledge
on commutative algebra will be required.
Lecture 2:
Initial ideals and triangulations of convex polytopes
Let
A be a
d x
n integer matrix and
PA
the convex hull of the columns of
A. Each initial ideal
of the toric ideal
IA gives a triangulation of
PA.
Such a triangulation is called a regular triangulation
of
PA. A unimodular triangulation is
a triangulation each of whose maximal face is of volume 1.
A flag triangulation is a triangulation each of whose minimal
nonface is an edge. A regular triangulation
is unimodular if and only if it comes from an initial ideal
generated by squarefree monomials. A regular triangulation
is flag if and only if it comes from an initial
ideal generated by quadratic monomials. In particular,
the convex polytope
PA possesses a regular
triangulation which is both unimodular and flag if and only if
the toric ideal
IA possesses an initial ideal which is
generated by squarefree quadratic monomials.
Let
G be a finite graph and
AG its vertex-edge incidence
matrix. The convex polytope
PAG is called
the edge polytope of
G. In the talk, we discuss
unimodular triangulations and flag triangulations of
edge polytopes of finite graphs.
Lecture 3:
Generic initial ideals and algebraic shifting
Algebraic shifting, introduced by Gil Kalai, is one of the
most powerful techniques in algebraic combinatorics on
convex polytopes. On the other hand, the generic initial
ideal turns out to be a fundamental tool in computational
commutative algebra. In the first half of the talk,
we discuss generic initial ideals briefly and introduce
symmetric algebraic shifting together with exterior algebraic
shifting in the language of generic initial ideals.
In the latter half of the talk, we report recent results
on algebraic shifting from viewpoints of both computational
commutative algebra and combinatorics.