I'm stuck in a property when I was reading proof of a theorem about polyhedral theory:

Every full dimensional, bounded and non-empty polyhedron in $\mathbb R^n$ has at least $n+1$ vertices.

A vertex is a point of a polyhedron such that we cannot write it as $\lambda x+(1-\lambda)y$ such that $\lambda \in (0,1)$.

Can anyone give me a hint to prove this property? I think I should consider the fact that this polyhedron is convex hull its vertices and with induction I should prove that convex hull of every $k$ elements is at most a $k-1$ dimensional space. But it doesn't make sense to me also these properties. Could you please help me to understand these fact truly?

  • $\begingroup$ Show you need $2$ points for $\mathbb{R}^1$ and then use induction on the number of dimensions. $\endgroup$ – David G. Stork Dec 2 '17 at 1:07
  • $\begingroup$ Really, I don't know how to apply induction here. I know that every bounded polyhedron is a polytope and every polytope is convex hull of a set of vectors and if the number of these vectors is less than $n+1$ then it is contained in a hyperplane and hyperplane is not a full dimensional subset(its volume is zero). But I dont know to show that the vertices of the polyhedron is the generated set of this polytope! $\endgroup$ – GhD Dec 2 '17 at 1:15
  • $\begingroup$ Two points determine a line segment (polytope in $\mathbb{R}^1$. If you want to make a polytope in $\mathbb{R}^2$, you need another point not on that line segment. In this way, $3$ points determine a polytope (triangular region) in $\mathbb{R}^2$. In order to make a polytope in $\mathbb{R}^3$, you need to add yet another point not in the triangular polytope. And, by induction, you need at least $n+1$ points to define a polytope in $\mathbb{R}^n$. $\endgroup$ – David G. Stork Dec 2 '17 at 1:24
  • $\begingroup$ Dear Mr. Stork I think this way is not correct. For example when you have 2 points in $\mathbb R^1$ than it doesn't mean to add another point not on that line segment to have a polytope( really it is better to say bounded non empty and full dimensional polyhedron or polytope) in $\mathbb R^2$ because the first two points were not in $\mathbb R^2$. I think it is not mathematically true this way. $\endgroup$ – GhD Dec 2 '17 at 1:36
  • $\begingroup$ You can embed the $2$ points in $\mathbb{R}^2$ and easily show that the resulting polyhedron is not "full dimensional" (as you state), and then add you additional point (properly) to show that the resulting polytope is full dimensional. $\endgroup$ – David G. Stork Dec 2 '17 at 2:12

Since you already know that a polyhedron is the convex hull of its vertices, the proof can proceed like this. Suppose the vertex set is $v_1, \dots, v_m$ with $m\le n$. The vectors $v_1-v_m,\dots, v_{m-1}-v_m$ span a linear subspace $W\subset \mathbb{R}^n$ of dimension at most $m-1$. Therefore, the points $v_1, \dots, v_m$ lie in the affine subspace $W+v_m$ of dimension at most $m-1 < n$. Since $W+v_m$ is a convex set, the convex hull of $v_1, \dots, v_m$ is contained in $W+v_m$ and therefore has empty interior.

  • $\begingroup$ Thank you for your answer. I am not very familiar with this topic. Could you please introduce a book or some other sources about polyhedral theory to me to study? $\endgroup$ – GhD Dec 2 '17 at 14:03
  • $\begingroup$ Anything with "convex hull" in it, like these notes $\endgroup$ – user357151 Dec 2 '17 at 15:06

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.