Neighborhood Complexes and Generating Functions for Affine Semigroups

Herbert Scarf and Kevin M. Woods
Additional contact information
Kevin M. Woods: University of Michigan

No 1458, Cowles Foundation Discussion Papers from Cowles Foundation for Research in Economics, Yale University

Abstract: Given a_{1}; a_{2},...a_{n} in Z^{d}, we examine the set, G, of all nonnegative integer combinations of these ai. In particular, we examine the generating function f(z) = Sum_{b in G}z^{b}. We prove that one can write this generating function as a rational function using the neighborhood complex (sometimes called the complex of maximal lattice-free bodies or the Scarf complex) on a particular lattice in Z^{n}. In the generic case, this follows from algebraic results of D. Bayer and B. Sturmfels. Here we prove it geometrically in all cases, and we examine a generalization involving the neighborhood complex on an arbitrary lattice.

Keywords: Integer programming; Complex of maximal lattice free bodies; Generating functions (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Pages: 24 pages
Date: 2004-04
Note: CFP 1169.
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in Discrete and Computational Geometry (2006), 35: 385-403

Downloads: (external link)
https://cowles.yale.edu/sites/default/files/files/pub/d14/d1458.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found

Related works:
Chapter: Neighborhood Complexes and Generating Functions for Affine Semigroups (2008)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cwl:cwldpp:1458

Ordering information: This working paper can be ordered from
Cowles Foundation, Yale University, Box 208281, New Haven, CT 06520-8281 USA
The price is None.

Access Statistics for this paper

More papers in Cowles Foundation Discussion Papers from Cowles Foundation for Research in Economics, Yale University Yale University, Box 208281, New Haven, CT 06520-8281 USA. Contact information at EDIRC.
Bibliographic data for series maintained by Brittany Ladd ().