How many vertices can a convex polytope have?

Question

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...

Answer 1

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}.$$

Answer 2

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.
    
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. Now Chapter 15 in the Handbook 3rd edition.