2
$\begingroup$

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

2 Answers 2

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.

  • 0
    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.2012-03-09
1

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