• Calendar

November 7, Tuesday
12:00 – 14:00

In this talk we give upper bounds for the number of vertices of the polyhedron $P(A,b)=\{x\in \mathbb{R}^d~:~Ax\leq b\}$ when the $m\times 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 $C^d$ vertices. These bounds are consequences of a more general theorem that the number of vertices of $P(A,b)$ is at most $d!\cdot W/D$, where $W$ is the volume of the convex hull of the zero vector and the row vectors of $A$, and $D$ is the smallest absolute value of any non-zero $d\times d$ subdeterminant of $A$.