19
$\begingroup$

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

$\endgroup$

2 Answers 2

23
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Jan, Do you have a source or proof for the equation you provided on April 12, 2013 which provides the maximum number of vertices given a particular number of half-spaces (k) and a particular ambient dimension (n)? Thank you! $\endgroup$ Feb 12 at 22:31
  • $\begingroup$ See for example the Wikipedia page on the "upper bound theorem": en.wikipedia.org/wiki/Upper_bound_theorem $\endgroup$ Feb 12 at 23:30
  • $\begingroup$ See, for example, Theorem 5.4.5 in Lectures on Discrete Geometry by Jiří Matoušek (link.springer.com/book/10.1007/978-1-4613-0039-7) $\endgroup$
    – Jan Kyncl
    Feb 13 at 2:51
13
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ I see that now that the answer Jan posted as I was preparing mine are essentially the same. $\endgroup$ Apr 13, 2013 at 0:18
  • $\begingroup$ Is there a direct way of finding vertex sets $V_d$ without calculating the dual ? Thanks $\endgroup$
    – denis
    Sep 11, 2019 at 10:49
  • $\begingroup$ @denis: That is called vertex enumeration in the literature. The Avis-Fukuda algorithm is now standard. $\endgroup$ Sep 11, 2019 at 12:09
  • $\begingroup$ Actually I want the H-form -- $A, b$ for which $Ax \leq b, x \geq 0$ is difficult to solve: many vertices but not necessarily cyclic polytope. Thanks anyway. $\endgroup$
    – denis
    Sep 13, 2019 at 9:36
  • $\begingroup$ You give here a $\Theta$ expression $n^{d/2}$ -- what would be the $O(n^{d/2})$ constant? Thanks. $\endgroup$
    – kloop
    May 21, 2022 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.