tripes3h

2022-07-09

A polyhedron P in ${R}^{n}$ is given by the system of m linear inequalities (of n variables). Furthermore, let P have k vertices (that is, k vectors satisfying all m constraints at least for n of which the equalities hold).
a) If m = 7; n = 2, might k be equal to: 0; 1; 7; 8; 23?
b) If m = 6; n = 3, might k be equal to: 0; 1; 6; 8; 9; 21?
c) If m = 8; n = 7, might k be equal to: 0; 1; 2; 7; 8; 9; 10?
d) If m = n = 6, might k be equal to: 0; 1; 2; 3?
e) If m = 4; n = 5, might k be equal to: 0; 1; 2?
Give an example if the answer is "yes" and explain why not if it is "no".

Brendan Bush

Expert

Unfortunately I don't know how to solve it correctly. But it seems like it's somehow related to Euler characteristic, which states that
$V-E+F=2$, for any convex polyhedron, where
$V$ - vertices, $E$ - edges, $F$ - faces of polyhedron.
We can assume that $E\le m$ and $F\le n$, therefore $E\le m+n-2$.
So for every k you chould check the inequality $k\le m+n-2$.
It looks like it's gonna work in many cases, if you have answers please compare them with this inequality.

vasorasy8

Expert

An upper bound on the number of vertices of a polyhedron given $m$ constraints in $n$ variables is $\left(\genfrac{}{}{0}{}{m}{n}\right)$. Consider a polygon in ${\mathbb{R}}^{2}$, for example: choosing any two lines gives you (at most) one point of intersection. The upper bound of $\left(\genfrac{}{}{0}{}{m}{n}\right)$ is very loose, though, since not every such point will necessarily be inside the polygon. In ${\mathbb{R}}^{2}$, a polygon determined by $m$ inequalities can have at most m vertices, which is much lower than $\left(\genfrac{}{}{0}{}{m}{2}\right)$.
A better bound, and one that can be met with equality for all $m,n$, is $\left(\genfrac{}{}{0}{}{m-⌊\frac{n+2}{2}⌋}{m-n}\right)$.

Do you have a similar question?