Combinatorial Commutative Algebra and Integer Programming

点击翻译按钮获取中文摘要

This research program concerns questions at the intersection ofcommutative algebra, integer programming, and discrete geometry. Thelink between these fields is made via toric ideals and their Groebnerbases. The first set of questions concern the characterization andconstruction of toric initial ideals without embedded primes. Answersto these questions will provide new structural results in the theoryof integer programming via the classical technique of grouprelaxations due to Gomory and will extend recent work in this area bySerkan Hosten and the proposer. The second set of questions concern the toric Hilbert scheme, a parameter space for all polynomial idealswith the same multi-graded Hilbert function as a given toric ideal. Acentral open question about these schemes is whether they areconnected. The proposer will work with Diane Maclagan on this connectivity question, building on their recent construction of agraph on the monomial ideals of the scheme which is connected if andonly if the scheme is connected. Over the past decade, the proposer has contributed to the developmentof several new theories in discrete optimization using algebraictechniques and has worked on the application of the resulting,non-traditional algorithms to practical problems. The research thathas contributed to these theories brings tools from algebra,combinatorics, optimization and discrete geometry to bear on problemsfrom all of these fields. The application of algebraic techniques hasled to new understanding in the field of integer programming, a branchof discrete optimization, but tools and ideas from optimization havealso led to new results in algebra. This interplay of ideas andtechniques has shed light on questions from each of these areas andpromises to lead to greater insight and advancement. The proposerworks with students on some of the computational aspects of theresearch and plans to involve students in the development of softwarethat implements these algorithms. The proposer is also interested incurriculum development in subject areas related to this research atthe University of Washington.