2

Please help with the problem:

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

Daniel
  • 73
  • 1
  • 5

1 Answers1

3

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.

com
  • 5,612
  • @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 01 '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 09 '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 09 '12 at 14:03