Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem

DOI10.1137/16M1100095MaRDI QIDQ4602859zbMATH OpenFDO

Authors Robert Hildebrand, Rico Zenklusen, Stephen R. Chestnut

Publication date 7 February 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Helly theoreminteger programminglattice points

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) Helly-type theorems and geometric transversal theory (52A35) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10)

Abstract: The recent paper "A quantitative Doignon-Bell-Scarf Theorem" by Aliev et al. generalizes the famous Doignon-Bell-Scarf Theorem on the existence of integer solutions to systems of linear inequalities. Their generalization examines the number of facets of a polyhedron that contains exactly $k$ integer points in $mathbb{R}^n$. They show that there exists a number $c(n,k)$ such that any polyhedron in $mathbb{R}^n$ that contains exactly $k$ integer points has a relaxation to at most $c(n,k)$ of its inequalities that will define a new polyhedron with the same integer points. They prove that $c(n,k)=O(k{2}^n)$. In this paper, we improve the bound asymptotically to be sublinear in $k$. We also provide lower bounds on $c(n,k)$, along with other structural results. For dimension $n=2$, our bounds are asymptotically tight to within a constant.

Recommendations

• A quantitative Doignon-Bell-Scarf theorem
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem
• On integer points in polyhedra
• Upper and lower bound results on the convex hull of integer points in polyhedra
• Disjunctive programming and relaxations of polyhedra

Cites work

• A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
• A quantitative Doignon-Bell-Scarf theorem
• A Theorem Concerning the Integer Lattice
• Additive combinatorics
• An observation on the structure of production sets with indivisibilities
• Arithmetic progressions in sets of small doubling
• Arithmetical progressions and the number of sums
• Convexity in cristallographical lattices
• Duality for mixed-integer convex minimization
• Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem
• Helly’s theorem: New variations and applications
• scientific article; zbMATH DE number 5149025 (Why is no real title available?)
• scientific article; zbMATH DE number 5302813 (Why is no real title available?)
• scientific article; zbMATH DE number 3770461 (Why is no real title available?)
• scientific article; zbMATH DE number 66675 (Why is no real title available?)
• scientific article; zbMATH DE number 2058507 (Why is no real title available?)
• scientific article; zbMATH DE number 4119933 (Why is no real title available?)
• scientific article; zbMATH DE number 866010 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Midpoints of Diagonals of Convex n-Gons
• Moving out the edges of a lattice polygon
• On defining sets of vertices of the hypercube by linear inequalities
• On maximal S-free sets and the Helly number for the family of S-convex sets
• Planar sets containing no three collinear points and non-averaging sets of integers
• Roth's theorem in many variables
• The convex hull of the integer points in a large ball
• The minimum area of convex lattice \(n\)-gons
• Three-term arithmetic progressions and sumsets
• Tight bounds on discrete quantitative Helly numbers
• Transversal numbers over subsets of linear spaces
• Über Integrale auf konvexen Körpern. I, II

Cited in

(8)

• A quantitative Doignon-Bell-Scarf theorem
• Discrete quantitative Helly-type theorems with boxes
• Tight bounds on discrete quantitative Helly numbers
• Quantitative Tverberg theorems over lattices and other discrete sets
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem
• Midpoints of vertex pairs of convex polytopes
• Extensions of discrete Helly theorems for boxes

This page was built for publication: Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem

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