Grobner bases of Point ConfigurationsAlgebra & Discrete Mathematics
|Speaker:||Prof. Shmuel Onn, Technion- Haifa Israel and UC Davis|
|Start time:||Tue, Oct 9 2001, 10:00AM|
In this talk I'll overview work joint with Bernd Sturmfels where we construct the State Polyhedron of any configuration of finitely many points in affine space. Its vertices then stand in bijection with the various reduced Grobner bases of the point configuration. Combining our characterization of all the reduced Groebner bases of a point configuration with a polynomial time procedure for enumerating the vertices of the State Polyhedron, we are able to provide a polynomial time algorithm for computing the Universal Grobner basis of the generic configuration in any fixed dimension. The talk will be self contained and is intended to provide a quick introduction to Grobner bases, Grobner fans and State polyhedra of polynomial ideals. I will mention some questions related to the non-generic case, as well as enumerative questions regarding improved bounds (I'll describe the recent best-so-far ones by Wagner and Remond).