On lattice width of lattice-free polyhedra and height of Hilbert bases

DOI10.1137/21M145416XMaRDI QIDQ5099099zbMATH OpenOpenAlexFDO

Authors Martin Henk, Stefan Kuhlmann, Robert Weismantel

Publication date 31 August 2022

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

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

zbMATH Keywords

diameter of finite abelian groupsHilbert basislattice pointslattice widthlattice-free polyhedra

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) (n)-dimensional polytopes (52B11) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10)

Abstract: We study the lattice width of lattice-free polyhedra given by $mathbfAmathbfxleqmathbfb$ in terms of $Delta(mathbfA)$, the maximal $nimesn$ minor in absolute value of $mathbfAinmathbb{Z}^{mimesn}$. Our main contribution is to link the lattice width of lattice-free polyhedra to the height of Hilbert bases and to the diameter of finite abelian groups. This leads to a bound on the lattice width of lattice-free pyramids which solely depends on $Delta(mathbfA)$ provided a conjecture regarding the height of Hilbert bases holds. Further, we exploit a combination of techniques to obtain novel bounds on the lattice width of simplices. A second part of the paper is devoted to a study of the above mentioned Hilbert basis conjecture. We give a complete characterization of the Hilbert basis if $Delta(mathbfA)=2$ which implies the conjecture in that case and prove its validity for simplicial cones.

Recommendations

• The height of minimal Hilbert bases
• On the height of the minimal Hilbert basis
• On the width of lattice-free simplices
• Hollow polytopes of large width
• Lattice-free simplices with lattice width \(2d - o(d)\)

Cites work

• A note on non-degenerate integer programs with small sub-determinants
• A strongly polynomial algorithm for bimodular integer linear programming
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• Distances between optimal solutions of mixed-integer programs
• Enumerating integer points in polytopes with bounded subdeterminants
• Generating abelian groups by addition only
• Geometry of the Minimal Solutions of a Linear Diophantine Equation
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• Integer program with bimodular matrix
• Integer Programming with a Fixed Number of Variables
• On integer programming with bounded determinants
• On the height of the minimal Hilbert basis
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Sparse Solutions of Linear Diophantine Equations
• The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
• The height of minimal Hilbert bases
• The support of integer optimal solutions
• Toric varieties

Cited in

(7)

• The height of minimal Hilbert bases
• Lattice-free simplices with lattice width \(2d - o(d)\)
• Enumeration and unimodular equivalence of empty delta-modular simplices
• New Bounds for the Integer Carathéodory Rank
• On the height of the minimal Hilbert basis
• Lattice angles of lattice polygons
• Combinatorial optimization. Abstracts from the workshop held November 10--15, 2024

This page was built for publication: On lattice width of lattice-free polyhedra and height of Hilbert bases

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