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

number of facets\(0/1\)-polytope

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.

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

(16)

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

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)