The University of Michigan Combinatorics Seminar
Winter 2008
March 14, 4:10-5:00, 3866 East Hall



The "reverse search" property of Gröbner fans

Anders Jensen

TU Berlin


Abstract

The Gröbner fan of a polynomial ideal I was defined by Mora and Robbiano in 1988. It is a collection of polyhedral cones indexing the reduced Gröbner bases of I. Independent of this definition Bayer and Morrison defined an essentially dual object: the state polytope of I. Indeed for any homogeneous ideal I a polytope can be constructed whose normal fan is the Gröbner fan of I. The "reverse search" technique by Avis and Fukuda is a clever, memoryless way of organizing the traversal of the edge graph of a polyhedron. In order to develop efficient algorithms for computing the Gröbner fan we may ask ourselves the following natural question: Is the Gröbner fan of any ideal the normal fan of a polyhedron? In this talk we show that the answer is no, but that the reverse search idea still applies. This is joint work with Komei Fukuda and Rekha Thomas.