×

Upper bounds on the maximal number of facets of 0/1-polytopes. (English) Zbl 0951.52007

A polytope is said to be 0/1-polytope if it has only vertices with 0/1-coordinates. The authors prove the following two upper bounds on the number of facets \(f(d)\) that a \(d\)-dimensional 0/1-polytope can have: \(f(d)\leq 2(d-1)!+2(d-1)\) and \(f(d)=O((d-2)!)\). The first bound is the best one currently known for small dimensions, while the second bound is the best known for large dimensions.

MSC:

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B11 \(n\)-dimensional polytopes
90C27 Combinatorial optimization

Software:

01poly
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Acketa, D. M.; Žunić, J. D., On the maximal number of edges of convex digital polygons included into an \(m\)×\(m\) -grid, J. Comb. Theory, Ser. A, 69, 358-368 (1995) · Zbl 0815.68112
[2] Aichholzer, O., Extremal properties of 0/1-polytopes of dimension 5 (1998)
[3] Polytopes—Combinatorics and Computation, Kalai, G.Ziegler, G. M. Birkhäuser-Verlag, Basel; Polytopes—Combinatorics and Computation, Kalai, G.Ziegler, G. M. Birkhäuser-Verlag, Basel
[4] Andrews, G. E., An asymptotic expression for the number of solutions of a general class of Diophantine equations, Trans. Am. Math. Soc., 99, 272-277 (1961) · Zbl 0113.03702
[5] Andrews, G. E., A lower bound for the volume of strictly convex bodies with many boundary lattice points, Trans. Am. Math. Soc., 106, 270-279 (1963) · Zbl 0118.28301
[6] Arnol ′ d, V. I., Statistics of integral convex polygons (in Russian), Funktsionalnyi Analiz i ego Prilozheniya, 14 (1980)
[7] Funct. Anal. Appl., 14, 79-81 (1980)
[8] Bárány, I.; Larman, D. G., The convex hull of the integer points in a large ball, Math. Annalen, 312, 167-181 (1998) · Zbl 0927.52020
[9] T. Christof, SMAPO—‘Small’ 0/1-polytopes in Combinatorial Optimization; T. Christof, SMAPO—‘Small’ 0/1-polytopes in Combinatorial Optimization · Zbl 0911.90280
[10] Jarnı́k, V., Über die Gitterpunkte auf konvexen Kurven, Math. Z., 24, 500-518 (1926) · JFM 51.0153.01
[11] Konyagin, S. V.; Sevast ′ yanov, K. A., A bound, in terms of its volume, for the number of vertices of a convex polyhedron when the vertices have integer coordinates (in Russian), Funktsionalnyi Analiz i ego Prilozheniya, 18 (1984) · Zbl 0548.52003
[12] Funct. Anal. Appl., 18, 11-13 (1984)
[13] U. Kortenkamp; U. Kortenkamp
[14] Kortenkamp, U.; Richter-Gebert, Jürgen; Sarangarajan, Aravamuthan; Ziegler, Günter M., Extremal properties of 0/1-polytopes, Discrete Comput. Geom., 17, 439-448 (1997) · Zbl 0881.52005
[15] Schmidt, W. M., Integer points on curves and surfaces, Monatsh. Math., 99, 45-72 (1985) · Zbl 0551.10026
[16] T. Thiele, 1991; T. Thiele, 1991
[17] Ziegler, G. M., Lectures on Polytopes (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0823.52002
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.