Fleiner, Tamás; Kaibel, Volker; Rote, Günter Upper bounds on the maximal number of facets of 0/1-polytopes. (English) Zbl 0951.52007 Eur. J. Comb. 21, No. 1, 121-130 (2000). 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. Reviewer: V.Alexandrov (Novosibirsk) Cited in 1 ReviewCited in 8 Documents MSC: 52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) 52B11 \(n\)-dimensional polytopes 90C27 Combinatorial optimization Keywords:0/1-polytope; exponential upper bound; volume Software:01poly PDFBibTeX XMLCite \textit{T. Fleiner} et al., Eur. J. Comb. 21, No. 1, 121--130 (2000; Zbl 0951.52007) 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.