Skip to main content

Seminar on Algebra and Geometry

Date:
-
Location:
112 Patterson Office Tower
Speaker(s) / Presenter(s):
Sonja Petrović, Illinois Institute of Technology

Title:  Bouquet algebra of toric ideals

Abstract: To any integer matrix A one can associate a toric ideal I_A, whose sets of generators are basic objects in discrete linear optimization, statistics, and graph/hypergraph sampling algorithms. The basic algebraic problem is that of implicitization: given the matrix A, find a set of generators with some given property (minimal, Groebner, Graver, etc.). Then there is a related problem of complexity: how complicated can these generators be? In general, it is known that Graver bases are much more complicated than minimal generators. But there are some classical families of toric ideals where these sets actually agree, providing very nice results on complexity and sharp degree bounds.

This talk is about combinatorial signatures of generating sets of I_A. For the special case when A is a 0/1 matrix, bicolored hypergraphs give the answer. It turns out that such hypergraphs give an intuition for constructing basic building blocks for the general case too. Namely, we introduce the bouquet graph and bouquet ideal of the toric ideal I_A, whose structure determines the Graver basis. This, in turn, leads to a complete characterization of toric ideas for which the following sets are equal: the Graver basis, the universal Groebner basis, any reduced Groebner basis and any minimal generating set. This generalizes many of the classical examples.