Hollow polytopes of large width
HTML articles powered by AMS MathViewer
- by Giulia Codenotti and Francisco Santos PDF
- Proc. Amer. Math. Soc. 148 (2020), 835-850 Request permission
Abstract:
We construct the first known hollow lattice polytopes of width larger than dimension: a hollow lattice polytope (resp., a hollow lattice simplex) of dimension $14$ (resp., $404$) and of width $15$ (resp., $408$). We also construct a hollow (nonlattice) tetrahedron of width $2+\sqrt 2$, and we conjecture that this is the maximum width among $3$-dimensional hollow convex bodies.
We show that the maximum lattice width grows (at least) additively with $d$. In particular, the constructions above imply the existence of hollow lattice polytopes (resp., hollow simplices) of arbitrarily large dimension $d$ and width $\simeq 1.14 d$ (resp., $\simeq 1.01 d$).
References
- Gennadiy Averkov and Amitabh Basu, Lifting properties of maximal lattice-free polyhedra, Math. Program. 154 (2015), no. 1-2, Ser. B, 81–111. MR 3421929, DOI 10.1007/s10107-015-0865-6
- Gennadiy Averkov, Jan Krümpelmann, and Stefan Weltge, Notions of maximality for integral lattice-free polyhedra: the case of dimension three, Math. Oper. Res. 42 (2017), no. 4, 1035–1062. MR 3722425, DOI 10.1287/moor.2016.0836
- Gennadiy Averkov, Christian Wagner, and Robert Weismantel, Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three, Math. Oper. Res. 36 (2011), no. 4, 721–742. MR 2855866, DOI 10.1287/moor.1110.0510
- Gennadiy Averkov and Christian Wagner, Inequalities for the lattice width of lattice-free convex sets in the plane, Beitr. Algebra Geom. 53 (2012), no. 1, 1–23. MR 2890359, DOI 10.1007/s13366-011-0028-8
- W. Banaszczyk, Inequalities for convex bodies and polar reciprocal lattices in $\mathbf R^n$. II. Application of $K$-convexity, Discrete Comput. Geom. 16 (1996), no. 3, 305–311. MR 1410163, DOI 10.1007/BF02711514
- Wojciech Banaszczyk, Alexander E. Litvak, Alain Pajor, and Stanislaw J. Szarek, The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces, Math. Oper. Res. 24 (1999), no. 3, 728–750. MR 1854250, DOI 10.1287/moor.24.3.728
- Sanjeeb Dash, Neil B. Dobbs, Oktay Günlük, Tomasz J. Nowicki, and Grzegorz M. Świrszcz, Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming, Math. Program. 145 (2014), no. 1-2, Ser. A, 483–508. MR 3207696, DOI 10.1007/s10107-013-0654-z
- Christian Haase and Günter M. Ziegler, On the maximal width of empty lattice simplices, European J. Combin. 21 (2000), no. 1, 111–119. Combinatorics of polytopes. MR 1737331, DOI 10.1006/eujc.1999.0325
- Martin Henk, Jürgen Richter-Gebert, and Günter M. Ziegler, Basic properties of convex polytopes, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 243–270. MR 1730169
- C. A. J. Hurkens, Blowing up convex sets in the plane, Linear Algebra Appl. 134 (1990), 121–128. MR 1060014, DOI 10.1016/0024-3795(90)90010-A
- Óscar Iglesias-Valiño and Francisco Santos, Classification of empty lattice 4-simplices of width larger than two, Trans. Amer. Math. Soc. 371 (2019), no. 9, 6605–6625. MR 3937339, DOI 10.1090/tran/7531
- Ravi Kannan and László Lovász, Covering minima and lattice-point-free convex bodies, Ann. of Math. (2) 128 (1988), no. 3, 577–602. MR 970611, DOI 10.2307/1971436
- John Milnor and Dale Husemoller, Symmetric bilinear forms, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 73, Springer-Verlag, New York-Heidelberg, 1973. MR 0506372
- M. Rudelson, Distances between non-symmetric convex bodies and the $MM^\ast$-estimate, Positivity 4 (2000), no. 2, 161–178. MR 1755679, DOI 10.1023/A:1009842406728
- András Sebő, An introduction to empty lattice simplices, Integer programming and combinatorial optimization (Graz, 1999) Lecture Notes in Comput. Sci., vol. 1610, Springer, Berlin, 1999, pp. 400–414. MR 1709397, DOI 10.1007/3-540-48777-8_{3}0
- G. K. White, Lattice tetrahedra, Canadian J. Math. 16 (1964), 389–396. MR 161837, DOI 10.4153/CJM-1964-040-2
Additional Information
- Giulia Codenotti
- Affiliation: Institut für Mathematik, Freie Universität Berlin, Germany
- Email: giulia.codenotti@fu-berlin.de
- Francisco Santos
- Affiliation: Department of Mathematics, Statistics and Computer Science, University of Cantabria, Santander, Spain
- MR Author ID: 360182
- ORCID: 0000-0003-2120-9068
- Email: francisco.santos@unican.es
- Received by editor(s): December 17, 2018
- Received by editor(s) in revised form: April 27, 2019, April 29, 2019, and May 27, 2019
- Published electronically: August 7, 2019
- Additional Notes: The authors were supported by the Einstein Foundation Berlin under grant EVF-2015-230 and, while they were in residence at the Mathematical Sciences Research Institute in Berkeley, California during the Fall 2017 semester, by the Clay Institute and the National Science Foundation (Grant No. DMS-1440140).
The work of the second author was also supported by project MTM2017-83750-P of the Spanish Ministry of Science (AEI/FEDER, UE) - Communicated by: Patricia L. Hersh
- © Copyright 2019 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 148 (2020), 835-850
- MSC (2010): Primary 52C07, 52B20; Secondary 52C17
- DOI: https://doi.org/10.1090/proc/14721
- MathSciNet review: 4052219