If a polytope has $d$ vertices in $k$ dimensions how many linear inequalities is required to describe it?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ It depends on the polytope. Do you mean the maximum with fixed $d, k$? $\endgroup$– Fedor PetrovCommented Apr 2, 2021 at 5:08
-
$\begingroup$ Smallest and maximum. $\endgroup$– TurboCommented Apr 2, 2021 at 5:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Since the span of $n$ points has dimension at most $n-1$, each face of dimension $k-1$ (hyperplane) must contain at least $k$ vertices. So the number of faces of maximal dimension $k-1$ is at most $$\frac{d!}{k!(d-k)!},$$ the binomial coefficient. This becomes an equality for simplices.
answered Apr 2, 2021 at 11:17
-
-
$\begingroup$ Say, if $k=2$, the answer is $d$, not $d(d-1)/2$ $\endgroup$ Commented Apr 2, 2021 at 12:03
-
$\begingroup$ @FedorPetrov What is the general situation for minimality? $\endgroup$– TurboCommented Apr 2, 2021 at 12:08
-
4$\begingroup$ Maximum number of facets is achieved for a cyclic polytope, this is a famous result by P. McMullen cambridge.org/core/journals/mathematika/article/… $\endgroup$ Commented Apr 2, 2021 at 12:52
-
2$\begingroup$ What Fedor says is of course true, but might be worth adding that the cyclic polytopes simultaneously maximize the face numbers of all dimensions at once. $\endgroup$ Commented Apr 2, 2021 at 18:40