Take the 2-minute tour ×

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

share|improve this question
@Henry, yes now that you say it I am becoming aware that I am talking about convex polyhedra –  Suedklee Aug 5 '12 at 15:13

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer

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)
share|improve this answer

Your Answer


