Combinatorial Commutative Algebra and Integer Programming

University Of Washington, Seattle WA

Investigators

Abstract

This research program concerns questions at the intersection of commutative algebra, integer programming, and discrete geometry. The link between these fields is made via toric ideals and their Groebner bases. The first set of questions concern the characterization and construction of toric initial ideals without embedded primes. Answers to these questions will provide new structural results in the theory of integer programming via the classical technique of group relaxations due to Gomory and will extend recent work in this area by Serkan Hosten and the proposer. The second set of questions concern the toric Hilbert scheme, a parameter space for all polynomial ideals with the same multi-graded Hilbert function as a given toric ideal. A central open question about these schemes is whether they are connected. The proposer will work with Diane Maclagan on this connectivity question, building on their recent construction of a graph on the monomial ideals of the scheme which is connected if and only if the scheme is connected. Over the past decade, the proposer has contributed to the development of several new theories in discrete optimization using algebraic techniques and has worked on the application of the resulting, non-traditional algorithms to practical problems. The research that has contributed to these theories brings tools from algebra, combinatorics, optimization and discrete geometry to bear on problems from all of these fields. The application of algebraic techniques has led to new understanding in the field of integer programming, a branch of discrete optimization, but tools and ideas from optimization have also led to new results in algebra. This interplay of ideas and techniques has shed light on questions from each of these areas and promises to lead to greater insight and advancement. The proposer works with students on some of the computational aspects of the research and plans to involve students in the development of software that implements these algorithms. The proposer is also interested in curriculum development in subject areas related to this research at the University of Washington.