Counting integer points in higher-dimensional polytopes

DOI10.1007/978-1-4939-7005-6_20MaRDI QIDQ2406337zbMATH OpenOpenAlexFDO

Authors Alexander Barvinok

Publication date 27 September 2017

Full work available at URL https://doi.org/10.1007/978-1-4939-7005-6_20

zbMATH Keywords

anti-concentration inequalitycontingency tableconvex optimizationconvex polytopeinteger latticemaximum entropy principletransportation polytope

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) (n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Review text

The paper under review deals with two computational problems concerning convex polyhedra: {\parindent= 0,7cm \begin{itemize}\item[1)] for a convex polyhedron \(P\subset \mathbb R^n\) defined as the intersection of an affine subspace with the non-negative orthant \(\mathbb R^n_+\), compute the number \(| P\cap\mathbb Z^n|\) of integer points in \(P\); \item [2)] for a convex polyhedron \(P\subset \mathbb R^n\) defined as the intersection of an affine subspace with the unit cube \([0,1]^n\), compute the number \(| P\cap\{ 0, 1\}^n|\) of \(0-1\) points in \(P\). \end{itemize}} The author discusses a family of heuristic formulae for computing approximately the desired quantities, which are derived by using an original probabilistic approach, c.f. [the author and \textit{J. A. Hartigan}, Adv. Appl. Math. 45, No. 2, 252--289 (2010; Zbl 1213.05015)]. For the entire collection see [Zbl 1377.52002].

Recommendations

• On integer points in polyhedra
• Integer points in polyhedra
• Integer points enumerator of hypergraphic polytopes
• Counting integer points of flow polytopes
• Counting integer points in polytopes associated with directed graphs
• The many aspects of counting lattice points in polytopes
• Counting integral points in polytopes via numerical analysis of contour integration
• Enumerating integer points in polytopes with bounded subdeterminants

Cited in

(20)

• On integer points in polyhedra
• Enumerating a subset of the integer points inside a Minkowski sum
• Counting polytopes via the Radon complex
• Counting integer points of flow polytopes
• Bounds on Kronecker coefficients via contingency tables
• Lower bounds for contingency tables via Lorentzian polynomials
• Counting integer points in polytopes associated with directed graphs
• Some estimates for the number of vertices of integer polyhedra
• scientific article; zbMATH DE number 4214137 (Why is no real title available?)
• Counting the Number of Integral Points in General n-Dimensional Tetrahedra and Bernoulli Polynomials
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• Enumerating Collinear Points in Higher Dimensions
• Counting integral points in polytopes via numerical analysis of contour integration
• The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
• Maximum entropy and integer partitions
• Durfee squares, symmetric partitions and bounds on Kronecker coefficients
• Computational complexity of counting coincidences
• Two classes of minimal generic fundamental invariants for tensors
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
• Counting integer points in parametric polytopes using Barvinok's rational functions

This page was built for publication: Counting integer points in higher-dimensional polytopes

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