# How many vertices in multi-dimensional space?

All I have is a $\mathbb{R}^n$ space and a number of restrictions which look like this $$\sum_{i=1}^n a_i x_i \ge a_0, \quad a_i \in \mathbb{R}$$

I would like to have a concept of vertices within my subspace and an ability to count them.

$\mathbb{R}^2$ case: since restrictions are geometrically half-planes I can draw lines on paper and see what happens. The simplest closed figure is a triangle, it has 3 vertices and needs a minimum of 3 restrictions to exist. Now every additional restriction can add no more than 1 additional vertice (this is obvious in 2-dimensional space). This means that for $k \ge 3$ restrictions there can exist no more than $k$ vertices.

$\mathbb{R}^3$ case: similarly the simplest closed figure appears to be a triangular pyramid, it has 4 vertices and needs a minimum of 4 restrictions to exist (I cannot visualize anything simpler than that). Now it gets a little more complicated with additional restrictions, but I'm taking a guess that for $k \ge 4$ restrictions there can exist no more than $(2k-4)$ vertices.

As you can see I need a strict formalization in order to even tackle this question for higher dimensions. What would you suggest? Also I'm pretty sure that there was a bunch of mathematicians who contemplated this before me, so simple references would also be appreciated.

-
You want to look into polyhedral theory. You'll find good introductions in linear programming books. Sets of the form you describe are called simplices and they can have a number of vertices that is exponential in the dimension. A quick Google search reveals homepages.ulb.ac.be/~aviolin/Cours.pdf but you'll want to look in books as well. – Dominique Feb 16 '13 at 22:59

The wikipedia page shows that $V \le 2F-4$ in three-dimensional space, so your guess was correct.