2
$\begingroup$

Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-spaces in $\mathbb R^d$. This is the $H$-representation of $P$.

Question. In terms of $n$ and $d$, what is a good upper-bound on the number of half-spaces in the smallest $H$-representation of $P$ ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

By the Upper Bound Theorem, the maximum number of $(d-1)$-dimensional faces of an $n$-vertex polytope is achieved by the cyclic polytopes. This number can be explicitly written via the Dehn-Sommerville equations.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks. For the record, if $f_k(P)$ is the number of $k$-dimensional faces of $P$, then the referenced Dehn-Sommerville equations (combined with Upper Bound Theorem) yield $f_{d-1}(P) \le 2{n-(d+1)/2 \choose n-d}$. $\endgroup$
    – dohmatob
    Commented Dec 27, 2021 at 9:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .