1
$\begingroup$

How many corners can a $n$-dimensinal convex polyhedron have at tops? Is it the same as the number of corners a $n$-dimensional simplex has?

EDIT: By polyhedron $P$, I mean, that for some matrix $A \in \mathbb{R}^{m,n}$, $P = \{ x\in \mathbb{R}^n \mid A x \leq b\}$ where $Ax \leq b$ is meant as $a_i^T x \leq b$. An alternative charakterization would be $P = \cap_{H \text{ is hyperplane}} H_{+}$, where $H_{+}$ is the half-room $\{x \in \mathbb{R}^n \mid \langle x, u \rangle \geq b\}$. ADDED convex

  • 0
    @Henry, yes now that you say it I am becoming aware that I am talking about *convex* polyhedra2012-08-05

2 Answers 2

6

A vertex of the polyhedron $P = \{x \in {\mathbb R}^n: Ax \le b\}$ is defined by the solution of $n$ of the equations $(A x)_i = b_i$ corresponding to linearly independent rows of $A$. In general, not all of those will be vertices, because they may violate other constraints. But the number of vertices is at most $m \choose n$.

EDIT: P. McMullen improved the upper bound to ${{m - \lfloor (n+1)/2 \rfloor} \choose {m-n}} + {{m - \lfloor (n+2)/2 \rfloor} \choose {m-n}}$ which turns out to be best possible. See P. McMullen, "The maximum number of faces of a convex polytope", Mathematika 17 (1970), pp. 179–184, and D. Gale, "Neighborly and cyclic polytopes", in Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 225–232, http://books.google.ca/books?hl=en&lr=&id=MuEFJR7Ek4EC&oi=fnd&pg=PA225

3

An $n$-dimensional polyhedron can have an arbitrarily large number of vertices. For regular convex polytopes the maxima are

Dimension   Maximum vertices      2         unlimited     3         20 (dodecahedron)     4        600 (120-cell)     5+       2^n (n-cube)