1
$\begingroup$

Suppose $Ax\leq b$ is a polyhedron, where the number of rows in $A$ is $r$, the vector $x$ lies in $\mathbb R^n$ and the rank of $A$ is $t$. Assume minimal number of hyperplane inequalities to define the polyhedron is $r'$.

Question. Can we exactly count the number of vertices in the polyhedron? If so, how to count it?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The answer varies according to the structure of the polytope. If you want the answer in particular cases, you can use vertex enumeration software, such as lrs .

Improve this answer
$\endgroup$
5
  • $\begingroup$ I provided update. $\endgroup$
    – Turbo
    Commented Apr 5, 2021 at 12:28
  • $\begingroup$ My answer is the same. The number of vertices is not a function of $n,r,t,r'$ even in 3-d. $\endgroup$
    – Brendan McKay
    Commented Apr 5, 2021 at 12:48
  • $\begingroup$ Can you please provide an example pairing to illustrate? $\endgroup$
    – Turbo
    Commented Apr 5, 2021 at 12:48
  • 3
    $\begingroup$ Make a square pyramid using 5 planes. It has 5 vertices. If you cut off the apex with an extra plane you get 8 vertices, but if you cut off one of the corners of the base you get 7 vertices. $\endgroup$
    – Brendan McKay
    Commented Apr 5, 2021 at 12:51
  • $\begingroup$ It's not my field of expertise, sorry. $\endgroup$
    – Brendan McKay
    Commented Apr 7, 2021 at 0:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .