The University of Michigan Combinatorics Seminar


Abstract 

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 a_{1} , . . . , a_{d}. 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 ddimensional 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. 