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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Dominique Feb 16 '13 at 22:59

This page might be a good place to start.

The "restriction" inequalities you mention define half-spaces, and the set of points that satisfy all the inequalities is a polyhedron (or "polytope") that is the intersection of these half-spaces. This polytope is convex, which makes lots of things easier.

Each of the restriction inequalities could (potentially) give rise to a face of the polytope. So, what you want, I think, is a relationship between the number of faces (F) and the number of vertices (V) of this polytope.

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

For higher-dimensional spaces, the answer is apparently given by the Dehn-Sommerville equations.

As the other answer mentioned, this topic is important in linear programming. The "restriction" inequalities are the constraints that the solution variables must satisfy, and the polytope is the "feasible" set of solutions. The classical algorithm for solving linear programming problems is called the simplex algorithm, and it essentially works by stepping from one vertex to another on the polytope. So, the linear programming literature probably has something interesting to say about this topic, too, and, depending on your background, it might be easier to understand than the mathematical literature.


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.