Neighborhood complexes and generating functions for affine semigroups

DOI10.1007/S00454-005-1222-YMaRDI QIDQ2492644zbMATH OpenOpenAlexFDO

Authors Herbert Scarf, Kevin M. Woods

Publication date 14 June 2006

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0403546

zbMATH Keywords

affine semigroupsFrobenius problemgenerating functionsNeighborhood complexestest sets

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Integer programming (90C10)

Abstract: Given a_1,a_2,...,a_n in Z^d, we examine the set, G, of all non-negative integer combinations of these a_i. In particular, we examine the generating function f(z)=sum_{bin 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.

Review text

For given integral vectors \(a_1,\dots,a_m\in\mathbb Z^n\) let \(G\) be the set of all non-negative integer combinations of these vectors, i.e., the additive semigroup generated by \(a_1,\dots,a_m\). By the work of \textit{A. Barvinok} and \textit{K. Woods} [J. Am. Math. Soc. 16, No. 4, 957--979 (2003; Zbl 1017.05008)] it is known that the generating function of \(G\), i.e., \(f(z)=\sum_{b\in G} z^b\) can be written as a short rational function. In the paper under review the authors present a (geometric) representation of \(f\) as a rational function using the so called neighborhood or \textit{H. E. Scarf} complex [see e.g., Math. Program. 79, No. 1--3(B), 355--368 (1997; Zbl 0887.90124)] of a certain lattice. If that lattice is ``generic, the result follows from more algebraic results of \textit{D. Bayer, I. Peeva} and \textit{B. Sturmfels } [Math. Res. Lett. 5, No. 1--2, 31--46 (1998; Zbl 0909.13010)]. Here the authors use a purely geometric approach which is based on topological properties of these complexes [cf. \textit{I. Bárány, H. E. Scarf} and \textit{D. Shallcross}, Math. Program. 80, No. 1(A), 1--15 (1998; Zbl 0894.90176)].

Recommendations

• Short rational generating functions for lattice point problems
• The complexity of generating functions for integer points in polyhedra and beyond
• Short generating functions for some semigroup algebras
• Lattice-point generating functions for free sums of convex sets
• Proportionally modular affine semigroups

This page was built for publication: Neighborhood complexes and generating functions for affine semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2492644)