# Need help with a Linear Programming homework.

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

-

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 \leq m$ and $F \leq n$, therefore $E \leq m+n-2$.

So for every k you chould check the inequality $k\leq m+n-2$.

It looks like it's gonna work in many cases, if you have answers please compare them with this inequality.

-
@con thanks for the replay. I don't have the answers; but when we go over it in class, I will be sure to post them here. – Daniel Mar 1 '12 at 15:14
This answer doesn't make any sense. Why would you assume that $E \leq m$ and $F \leq n$? (Counterexample: a cube is determined by 6 inequalities in 3 unknowns. Yet $E = 12 \not \leq 6$, and $F = 6 \not \leq 3$.) – Théophile Mar 9 '12 at 14:01
Furthermore, you don't want a bound that "looks like it's gonna work in many cases", you want a bound that you can prove will work in all cases. – Théophile Mar 9 '12 at 14:03

An upper bound on the number of vertices of a polyhedron given $m$ constraints in $n$ variables is $m \choose n$. 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 $m \choose n$ 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 $m \choose 2$.

A better bound, and one that can be met with equality for all $m, n$, is ${m - \lfloor{{n+1} \over 2} \rfloor} \choose {m-n}$ + ${m - \lfloor{{n+2} \over 2} \rfloor} \choose {m-n}$.

-