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$ ?

$\endgroup$

1 Answer 1

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.

$\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

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.