Upper Bound on the Number of Vertices of Polyhedra with 0,1-Constraint Matrices

2005/07/14 by Khaled Elbassioni, Elbassioni, Khaled, Zvi Lotker +3
Computer Science · Engineering · Mathematics · #Computational Geometry (cs.CG) #Digital Image Processing Techniques #FOS: Computer and information sciences #G.1.6 #Graph theory and applications #cs.CG #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.cs/0507038

3 pages

arxiv created 2005/07/14 · openalex publication_date 2005/07/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this note we show that the maximum number of vertices in any polyhedron P=\x∈ ℝ^d : Ax≤ b\ with 0,1-constraint matrix A and a real vector b is at most d!.

Related

• Convex lattice polygonal lines with a constrained number of vertices
• Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices
• The smallest mono-unstable, homogeneous convex polyhedron has at least 7 vertices
• A Problem of Erdös Concerning Lattice Cubes
• A bound for the number of vertices of a polytope with applications