On the diameter of lattice polytopes. (English) Zbl 1342.52014
Let \(P\) be a polytope and let \(G\) be its 1-skeleton. The distance between two vertices of \(G\) is the minimal possible number of edges for broken lines in \(G\) with endpoints in these two vertices. The diameter of \(G\) is the maximal distance between two vertices in \(G\).
In this paper the authors show that the diameter of a \(d\)-dimensional lattice polytope in \([0,k]^n\) is at most \(\lfloor (k-12)d\rfloor\). In particular this result implies that the diameter of a \(d\)-dimensional half-integral polytope is at most \(\lfloor \frac32 d\rfloor\). In addition the authors show the tightness of this bound for half-integral polytopes for every \(d\).
In this paper the authors show that the diameter of a \(d\)-dimensional lattice polytope in \([0,k]^n\) is at most \(\lfloor (k-12)d\rfloor\). In particular this result implies that the diameter of a \(d\)-dimensional half-integral polytope is at most \(\lfloor \frac32 d\rfloor\). In addition the authors show the tightness of this bound for half-integral polytopes for every \(d\).
Reviewer: Oleg Karpenkov (Liverpool)
MSC:
| 52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |
| 90C05 | Linear programming |
References:
| [1] | Abeledo, H.G., Rothblum, U.G.: Stable matchings and linear inequalities. Discrete Appl. Math. 54, 1-27 (1994) · Zbl 0820.90090 · doi:10.1016/0166-218X(94)90130-9 |
| [2] | Balinski, M.L.: Integer programming: methods, uses, computation. Manage. Sci. Ser. A 12, 253-313 (1965) · Zbl 0129.12004 |
| [3] | Balog, A., Bárány, I.: On the convex hull of the integer points in a disc. In: Proceedings of the Seventh Annual Symposium on Computational Geometry, SCG ’91, pp. 162-165. ACM, New York, NY, USA (1991) · Zbl 0746.52017 |
| [4] | Bonifas, N., Di Summa, M., Eisenbrand, F., Hähnle, N., Niemeier, M.: On sub-determinants and the diameter of polyhedra. Discrete Comput. Geom. 52(1), 102-115 (2014) · Zbl 1310.52013 · doi:10.1007/s00454-014-9601-x |
| [5] | Brønsted, A.: An Introduction to Convex Polytopes. Springer, Berlin (1983) · Zbl 0509.52001 · doi:10.1007/978-1-4612-1148-8 |
| [6] | Chena, X., Ding, G., Hu, X., Zang, W.: The maximum-weight stable matching problem: duality and efficiency. SIAM J. Discrete Math. 26(3), 1346-1360 (2012) · Zbl 1282.90105 · doi:10.1137/120864866 |
| [7] | Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Algorithms and Combinatorics. Springer, Berlin (1997) · Zbl 1210.52001 · doi:10.1007/978-3-642-04295-9 |
| [8] | Gijswijt, D., Pap, G.: An algorithm for weighted fractional matroid matching. J. Comb. Theory Ser. B 103, 509-520 (2013) · Zbl 1301.05057 · doi:10.1016/j.jctb.2013.05.004 |
| [9] | Kleinschmidt, P., Onn, S.: On the diameter of convex polytopes. Discrete Math. 102, 75-77 (1992) · Zbl 0762.52004 · doi:10.1016/0012-365X(92)90349-K |
| [10] | Naddef, D.J.: The Hirsch conjecture is true for \[(0,1)(0,1)\]-polytopes. Math. Program. 45, 109-110 (1989) · Zbl 0684.90071 · doi:10.1007/BF01589099 |
| [11] | Naddef, D.J., Pulleyblank, W.R.: Hamiltonicity in \[(0,1)(0,1)\]-polyhedra. J. Comb. Theory Ser. B 37(1), 41-52 (1984) · Zbl 0544.05058 · doi:10.1016/0095-8956(84)90043-1 |
| [12] | Padberg, M.: The boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139-172 (1989) · Zbl 0675.90056 · doi:10.1007/BF01589101 |
| [13] | Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986) · Zbl 0665.90063 |
| [14] | Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Berlin (2003) · Zbl 1041.90001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
