The many aspects of counting lattice points in polytopes

Barvinok's algorithm Ehrhart quasipolynomial Gelfand-Tsetlin pattern knapsack problems lattice point network flows rational polytope transportation polytope

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Lattices and convex bodies (number-theoretic aspects) (11H06) Lattice points in specified regions (11P21) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Review text

This well-written survey discusses applications of lattice-point enumeration problems in convex rational polytopes. Any such counting problem can be formulated in terms of the function \[ \phi_A(b) = \# \left\{ x \in {\mathbb Z}_{ \geq 0 }^n : \;Ax = b \right\} , \] for some integral \(d \times n\) matrix \(A\) and \(b \in {\mathbb Z}^d\). The author surveys some specific applications, such as knapsack problems, integral network flows, transportation polytopes and contingency tables, magic squares, Gelfand-Tsetlin patterns, and Hilbert series of monomial algebras. The paper gives the main structure theorem about \(\phi_A(b)\), namely that this function is a piecewise-defined quasipolynomial [\textit{B. Sturmfels}, J. Comb. Theory, Ser. A 72, No. 2, 302--309 (1995; Zbl 0837.11055)]. A fundamental specialization of this counting function is given by \(\phi_A(tb)\) for a fixed \(b\); hence \(t\) becomes an integral parameter which can be thought of as a dilation factor of the polytope \(\left\{ x \in {\mathbb Z}_{ \geq 0 }^n : \;Ax = b \right\}\). If this polytope has integral vertices, Ehrhart's theorem asserts that \(\phi_A(tb)\) is a polynomial in \(t\) whose leading term is the volume of \(P\) [\textit{E. Ehrhart}, C. R. Acad. Sci., Paris 254, 616--618 (1962; Zbl 0100.27601)]. The author finishes with a description of Barvinok's algorithm, which computes the lattice-point count for a rational polytope in fixed dimension in polynomial time. The paper concludes with some alternative algorithmic approaches and a brief discussion of lattice-point problems for regions other than convex polytopes.

Recommendations

Cites work

Cited in

(64)

Describes a project that uses

Uses Software

LattE

This page was built for publication: The many aspects of counting lattice points in polytopes

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