Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
@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
add comment

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.