A polyhedron P in R n is given by the system of m linear inequalities...
A polyhedron P in 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".
Answer & Explanation
Unfortunately I don't know how to solve it correctly. But it seems like it's somehow related to Euler characteristic, which states that
, for any convex polyhedron, where
- vertices, - edges, - faces of polyhedron.
We can assume that and , therefore .
So for every k you chould check the inequality .
It looks like it's gonna work in many cases, if you have answers please compare them with this inequality.
An upper bound on the number of vertices of a polyhedron given constraints in variables is . Consider a polygon in , for example: choosing any two lines gives you (at most) one point of intersection. The upper bound of is very loose, though, since not every such point will necessarily be inside the polygon. In , a polygon determined by inequalities can have at most m vertices, which is much lower than .
A better bound, and one that can be met with equality for all , is .