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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Polyhedral_combinatorics#Equalities_and_inequalities) 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](http://en.wikipedia.org/wiki/Dehn%E2%80%93Sommerville_equations) but I am not quite experienced enough and maybe it's a completely wrong way to look at this problem... 



How many vertices can a convex polytope have?
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](http://en.wikipedia.org/wiki/Dual_polytope) of the [cyclic polytope](http://en.wikipedia.org/wiki/Cyclic_polytope) with $k$ vertices. More generally, by the dual polytope of any [neighborly polytope](http://en.wikipedia.org/wiki/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}.$$


