Upper bounds on the maximal number of facets of 0/1-polytopes
type: Item
instance of: scholarly article
title: Upper bounds on the maximal number of facets of 0/1-polytopes
zbMATH Open document ID: 0951.52007
author: Tamás Fleiner
author: Volker Kaibel
author: Günter Rote
published in: European Journal of Combinatorics
publication date: 2000-12-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1406283
zbMATH Keywords: 0/1-polytope
zbMATH Keywords: exponential upper bound
zbMATH Keywords: volume
reviewed by: Victor Alexandrov
describes a project that uses: 01poly
MaRDI profile type: Publication
OpenAlex ID: W2023565414
cites work: On the maximal number of edges of convex digital polygons included into an \(m \times m\)-grid
cites work: An Asymptotic Expression for the Number of Solutions of a General Class of Diophantine Equations
cites work: A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
cites work: Statistics of integral convex polygons
cites work: The convex hull of the integer points in a large ball
cites work: Q4398725
cites work: A bound, in terms of its volume, for the number of vertices of a convex polyhedron when the vertices have integer coordinates
cites work: Extremal properties of \(0/1\)-polytopes
cites work: Integer points on curves and surfaces
cites work: Lectures on Polytopes
DOI: 10.1006/EUJC.1999.0326
Recommended article: On the Maximal Number of Facets of 0/1 Polytopes
Recommended article: Lower bound for the maximal number of facets of a 0/1 polytope
Recommended article: On 0-1 polytopes with many facets
Recommended article: Upper bounds for the number of facets of a simplicial complex
Recommended article: Upper bound on the number of vertices of polyhedra with 0,1-constraint matrices
Recommended article: Extremal properties of \(0/1\)-polytopes
Recommended article: On the 0,1 facets of the set covering polytope
Recommended article: The maximum number of complementary facets of a simplicial polytope
Recommended article: Q3697819
Recommended article: Q3974990
description: scientific article; zbMATH DE number 1406283