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

DOI10.1007/S00454-005-1159-1zbMATH Open1085.52008arXivmath/0406125OpenAlexW1983045691MaRDI QIDQ2571320FDOQ2571320

Authors: Dimitris Gatzouras, Giannopoulos Apostolos, Nikolaos Markoulakis 

Publication date: 1 November 2005

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

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.

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

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

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)

Cited In (16)

• 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
• Title not available (Why is that?)
• The convex hull of random points on the boundary of a simple polytope

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)