Generating Functions for Sets of Lattice Points

Kevin Woods

University of Michigan Ann Arbor

October 17,
refreshments at 3:45pm


Many interesting sets can be expressed as the projection of the set integer points in a polyhedron. The Frobenius semigroup is a good example: let S be the set of all numbers representable as a nonnegative integer combination of given coprime positive integers a_1,...,a_d. What is the largest integer not in S? How many positive integers are not in S? For any fixed d, these questions and others admit polynomial time algorithms. Our main tool is the following theorem: for fixed d, the generating function of the projection of the set of integer points in a d-dimensional polytope is computable in polynomial time. We use this to find the generating function of S, as well as of other interesting sets of lattice points, such as minimal Hilbert bases and test sets for integer programming.

Speaker's Contact Info: kmwoods(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on September 22, 2003 at 03:37 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.