Back to Search
Start Over
On Lattice Width of Lattice-Free Polyhedra and Height of Hilbert Bases
- Source :
- SIAM Journal on Discrete Mathematics. 36:1918-1942
- Publication Year :
- 2022
- Publisher :
- Society for Industrial & Applied Mathematics (SIAM), 2022.
-
Abstract
- We study the lattice width of lattice-free polyhedra given by $\mathbf{A}\mathbf{x}\leq\mathbf{b}$ in terms of $\Delta(\mathbf{A})$, the maximal $n\times n$ minor in absolute value of $\mathbf{A}\in\mathbb{Z}^{m\times n}$. 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(\mathbf{A})$ 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(\mathbf{A}) = 2$ which implies the conjecture in that case and prove its validity for simplicial cones.
Details
- ISSN :
- 10957146 and 08954801
- Volume :
- 36
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....73bfa1a0a86c7afc8b6e572e4fcb6b62