"Neighborhood complexes and rational generating functions"

Kevin Woods
Oberlin College

Thursday, April 1, 2010
2:00 pm
745 Patterson Office Tower

Abstract:

One approach to integer programming (maximizing an objective function across all feasible integer points satisfying a set of linear inequalities) is to start at some feasible integer point and continue stepping to a nearby feasible integer point that is better according to our objective function. If the set of possible nearby points is chosen correctly, using Herbert Scarf's definition of neighbors, we will eventually arrive at the desired optimum integer point.

Consider the integer points in a polytope and connect with an edge every pair who are neighbors. This gives the set of edges of a useful simplicial complex called the neighborhood complex. Using the fact that the neighborhood complex is contractible, we can compute generating functions for the following types of sets: those defined as the projection of the set of integer points of a polyhedron.

As a concrete example of this sort of set, suppose we are given relatively prime positive integers a_1, ... ,a_d, and define S to be the set of integers that can be written as a nonnegative integer combination of these a_i. We'd like to answer questions like what is the largest integer not in S and how many integers are not in S. These questions can be attacked via generating functions.

This talk builds on joint work with Herbert Scarf.