Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Generating functions for Sets of Lattice Points

Algebra & Discrete Mathematics

Speaker: Kevin Woods, Univ. of Michigan Mathematics
Location: 693 Kerr
Start time: Fri, Jan 17 2003, 12:10PM

We present 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 can use this theorem to find the generating functions for some interesting sets of lattice points, such as minimal Hilbert bases, test sets for integer programming, and the set of all numbers representable as a nonnegative integer combination of given coprime integers. As a consequence, we can answer related questions (for example, what is the cardinality of these sets?) quickly.