Lower bound for the maximal number of facets of a 0/1 polytope

DOI10.1007/S00454-005-1159-1MaRDI QIDQ2571320zbMATH OpenOpenAlexFDO

Authors Dimitris Gatzouras, Giannopoulos Apostolos, Nikolaos Markoulakis

Publication date 1 November 2005

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0406125

zbMATH Keywords

\(0/1\)-polytopenumber of facets

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Abstract: We show that there exist 0/1 polytopes in R^n with as many as (cn / (log n)^2)^(n/2) facets (or more), where c>0 is an absolute constant.

Review text

Improving on earlier work of \textit{I. Bárány} and \textit{A. Pór} [Adv. Math.~161, 209--228 (2001; Zbl 0988.52014)], the authors show the following. Let \(f_{n-1}(P)\) denote the number of facets of an \(n\)-polytope \(P\). Then there exists an absolute constant \(c > 0\) such that there is, for each \(n\), an \(n\)-dimensional \(0/1\)-polytope \(P\) (that is, with vertices in \(\{0,1\}^n\)), for which \[ f_{n-1}(P) \geq \left(\frac{cn}{\log^2n}\right)^{n/2}. \] In a note added in proof, they announce an improvement of this result, with the term \(\log^2n\) replaced by \(\log n\).

Recommendations

• On the Maximal Number of Facets of 0/1 Polytopes
• Upper bounds on the maximal number of facets of 0/1-polytopes
• Extremal properties of 0/1-polytopes
• scientific article; zbMATH DE number 1538123
• On 0-1 polytopes with many facets

Cited in

(18)

• Threshold for the volume spanned by random points with independent coordinates
• Stability properties of neighbourly random polytopes
• New results on lower bounds for the number of \((\leq k)\)-facets
• McMullen's conditions and some lower bounds for general convex polytopes
• Extremal properties of 0/1-polytopes
• Upper bounds on the maximal number of facets of 0/1-polytopes
• A bound for the number of vertices of a polytope with applications
• Revlex-initial 0/1-polytopes
• How to recycle your facets
• Equivalence classes of full-dimensional 0/1-polytopes with many vertices
• The convex hull of random points on the boundary of a simple polytope
• Extremal edge polytopes
• scientific article; zbMATH DE number 1538123 (Why is no real title available?)
• On the Maximal Number of Facets of 0/1 Polytopes
• A Large Deviations Approach to the Geometry of Random Polytopes
• On 0-1 polytopes with many facets
• Sharp estimates for the Cramér transform of log-concave measures and geometric applications
• Upper bound on the number of vertices of polyhedra with 0,1-constraint matrices

This page was built for publication: Lower bound for the maximal number of facets of a 0/1 polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2571320)