2
$\begingroup$

As the title say's: Imagine a full-dimensional convex polytope. Is there a lower bound (or even exact formula) for the minimum number of facets the polytope has?

$\endgroup$
3
$\begingroup$

The lower bound is realized by a simplex, so the answer would be $n+1$ in dimension $n$.

You should be able to prove it by taking $n+1$ extreme points of the convex polytope. That gives you a simplex. Show that adding points to that, you are adding faces.

$\endgroup$
  • $\begingroup$ Thank you. Wouldn't it suffice to say that a full-dimensional polytope needs at least 2 extreme points which in turn means that we need to have at least n+1 irredundant inequalities (since each extreme point sets n inequalities to equalities). Each of these corresponds to one facet. Are there any arguments missing? $\endgroup$ – user1742364 Nov 18 '13 at 21:29
  • $\begingroup$ Sorry, I don't quite follow. 2 extreme points seems too few to me to fix anything -- in theory there is a continuum of inequalities that 2 extreme points satisfy. But maybe I don't quite understand your argument. $\endgroup$ – arsmath Nov 18 '13 at 23:49
  • $\begingroup$ Okay, once again :-) We need at least two extreme points: If the polytope consisted of only one extreme point, it would have dimension 0 and thus wouldn't be full-dimensional. On the other hand, an extreme point is determined by setting a set of n irredundant inequalities to equality (face of dimension 0). So we need 2 different sets of inequalities while each set contains n elements. Thus, the minimum number of inequalities is n+1. Each of these inequalities determines in turn a facet when it is set to equality. That's my argument. Are there any mistakes? $\endgroup$ – user1742364 Nov 19 '13 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.