Discrete CATS Seminar
####
**
**#####
U N I V E R S I T Y
O F
K E N T U C K Y

DISCRETE
CATS
SEMINAR

WHERE CATS =
COMBINATORICS,
ALGEBRA,
TOPOLOGY
&
STATISTICS!

845 PATTERSON OFFICE TOWER

SPRING 2010

##
"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.