Upper bound on the number of vertices of polyhedra with 0, 1-constraint matrices
In this note we give upper bounds for the number of vertices of the polyhedron P (A, b)={x∈
Rd: Ax⩽ b} when the m× d constraint matrix A is subjected to certain restriction. For instance,
if A is a 0/1-matrix, then there can be at most d! vertices and this bound is tight, or if the
entries of A are non-negative integers so that each row sums to at most C, then there can be
at most Cd vertices. These bounds are consequences of a more general theorem that the
number of vertices of P (A, b) is at most d!⋅ W/D, where W is the volume of the convex hull of …
Rd: Ax⩽ b} when the m× d constraint matrix A is subjected to certain restriction. For instance,
if A is a 0/1-matrix, then there can be at most d! vertices and this bound is tight, or if the
entries of A are non-negative integers so that each row sums to at most C, then there can be
at most Cd vertices. These bounds are consequences of a more general theorem that the
number of vertices of P (A, b) is at most d!⋅ W/D, where W is the volume of the convex hull of …