Generating Functions for Sets of Lattice Points
University of Michigan Ann Arbor
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)umich.edu
Return to seminar home page
Page loaded on September 22, 2003 at 03:37 PM.
Copyright © 1998-99, Sara C. Billey.
All rights reserved.