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 |
Description
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.