Large Shadows from Sparse Inequalities

Abstract

The d-dimensional Goldfarb cube is a polytope with the property that all its 2^d vertices appear on some \emph{shadow} of it (projection onto a 2-dimensional plane). The Goldfarb cube is the solution set of a system of 2d linear inequalities with at most 3 variables per inequality. We show in this paper that the d -dimensional Klee-Minty cube --- constructed from inequalities with at most 2 variables per inequality --- also has a shadow with 2^d vertices. In contrast, with one variable per inequality, the size of the shadow is bounded by 2d.