Improved bounds on the diameter of lattice polytopes
| Autor: | Lionel Pournin, Antoine Deza |
|---|---|
| Přispěvatelé: | Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2017 |
| Předmět: |
Conjecture
General Mathematics 010102 general mathematics Metric Geometry (math.MG) Polytope 0102 computer and information sciences [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] 01 natural sciences Minkowski addition Combinatorics Mathematics - Metric Geometry Optimization and Control (math.OC) 010201 computation theory & mathematics Lattice (order) [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) 0101 mathematics Mathematics - Optimization and Control ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Acta Mathematica Hungarica Acta Mathematica Hungarica, Springer Verlag, In press, ⟨10.1007/s10474-017-0777-4⟩ |
| ISSN: | 1588-2632 0236-5294 |
| DOI: | 10.1007/s10474-017-0777-4 |
| Popis: | We show that the largest possible diameter $\delta(d,k)$ of a $d$-dimensional polytope whose vertices have integer coordinates ranging between $0$ and $k$ is at most $kd-\lceil2d/3\rceil$ when $k\geq3$. In addition, we show that $\delta(4,3)=8$. This substantiates the conjecture whereby $\delta(d,k)$ is at most $\lfloor(k+1)d/2\rfloor$ and is achieved by a Minkowski sum of lattice vectors. Comment: 14 pages, 1 figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink