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

Question

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 &quot;yes&quot; and explain why not if it is &quot;no&quot;.

Brendan Bush · Accepted Answer

Unfortunately I don&#039;t know how to solve it correctly. But it seems like it&#039;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&#039;s gonna work in many cases, if you have answers please compare them with this inequality.

vasorasy8 · Accepted Answer

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