A polyhedron P in R n is given by the system of m linear inequalities...





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".

Answer & Explanation

Brendan Bush

Brendan Bush


2022-07-10Added 14 answers

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 m and F n, therefore E m + n 2.
So for every k you chould check the inequality k m + n 2.
It looks like it's gonna work in many cases, if you have answers please compare them with this inequality.



2022-07-11Added 2 answers

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

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?