The University of Michigan Combinatorics Seminar
Winter 2003
January 10, 4:10-5:00, 3866 East Hall

The Frobenius problem and generating functions

Kevin Woods

University of Michigan


I will talk about several variations of the Frobenius problem. For example, let S be the set of all numbers representable as a nonnegative integer combination of given coprime positive integers a1 , . . . , ad. How many positive integers are not in S? For any fixed d, this problem and others admit polynomial time algorithms. The 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.