Generating functions for Sets of Lattice PointsAlgebra & Discrete Mathematics
|Speaker:||Kevin Woods, Univ. of Michigan Mathematics|
|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.