Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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