2

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?

user1742364
  • 196

1 Answers1

3

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.

arsmath
  • 2,073
  • 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? – user1742364 Nov 18 '13 at 21:29
  • 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. – arsmath Nov 18 '13 at 23:49
  • 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?

     – user1742364 Nov 19 '13 at 08:57