Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

One has an $n$-dimensional convex polytope $P$ represented by an intersection of half-spaces:

\begin{equation}H_i = \{ (x_1,x_2, \ldots,x_n) \in \mathbb{R}^n \mid \sum_{j=1}^n a_{ij} x_j \ge a_{i0}, \ a_{ij} \in \mathbb{R} \}, \ i = \overline{1,k} \end{equation} \begin{equation}P = \{ X \in \mathbb{R}^n \mid X \in \bigcap_{i=1}^k H_i \} \end{equation}

Then let's say that $(v_1,v_2,\ldots,v_n) \in P$ is a vertex if we can find at least $n$ subspaces (out of $k$) such that \begin{equation}\sum_{j=1}^n a_{\tilde i j} v_j = a_{\tilde i 0}, \quad \text{ for some } \tilde i \in \{ 1,2, \ldots , k\} \end{equation}

Now let's get to the point. It is known that we must have at least $k = n+1$ subspaces in order to construct a closed convex polytope. In this initial case it'd be a simplex having $n+1=|V|$ vertices (here $V$ is a set of vertices).

We can obviously introduce any number of somewhat trivial additional subspaces and stay at $|V|=n+1$ vertices, but I am interested in the maximum number of vertices for any given number of subspaces $k>n$ in $n$-dimensional space.


$\mathbb{R}^2$ case: since restrictions are geometrically half-planes one 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: $\max |V| = k.$

$\mathbb{R}^3$ case: similarly the simplest closed figure is a triangular pyramid, it has 4 vertices and needs a minimum of 4 restrictions to exist. Now it gets a little more complicated with additional restrictions, but what follows from fiddling with Euler characteristic is that for $k \ge 4$ restrictions there can exist no more than $(2k-4)$ vertices: $\max |V| = 2k-4.$

$\mathbb{R}^n$ case: I only understand clearly that $\max_{k = n+1} |V| = n+1.$ What happens after introducing additional restrictions is hard to conceive.

How can I generalize it? I hoped to draw some conclusions from Dehn–Sommerville equations but I am not quite experienced enough and maybe it's a completely wrong way to look at this problem...

share|improve this question
add comment

2 Answers

up vote 7 down vote accepted

Using $k$ half-spaces, the polytope has at most $k$ facets. For a fixed number of facets, the number of vertices is maximized, for example, by the dual polytope of the cyclic polytope with $k$ vertices. More generally, by the dual polytope of any neighborly polytope with $k$ vertices. This maximum number of vertices is equal to $${k-\lceil n/2 \rceil \choose \lfloor n/2 \rfloor} + {k-\lfloor n/2 \rfloor - 1 \choose \lceil n/2 \rceil - 1}.$$

share|improve this answer
add comment

What you call $n$ in your posting is often called $d$ in the literature, but I will stick with your notation. So $n$ is the dimension. Let $V$ be the number of vertices, and $k$ the number of facets. Then $V = \Theta( k ^ {\lfloor n/2 \rfloor} )$. More precisely, the maximum $V$ is given by McMullen's Upper Bound Theorem, realized by duals of cyclic polytopes. Cyclic polytopes maximize the number of facets for a fixed number of vertices, so their duals maximize the number of vertices for a fixed number of facets.
     CyclicPolytope
See, e.g.,

"Basic Properties Of Convex Polytopes." Martin Henk, Jürgen Richter-Gebert, and Günter M. Ziegler. Handbook of Discrete and Computational Geometry, Chapter 16. CRC Press. 2004. (CiteSeer link)

share|improve this answer
    
I see that now that the answer Jan posted as I was preparing mine are essentially the same. –  Joseph O'Rourke Apr 13 '13 at 0:18
add comment

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.