0
$\begingroup$

Consider polytopes

$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$ $$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$ $$B[z_{1},z_{2},z]'\leq c$$ having vertex count $v_1,v_2$ and $v$ respectively.

We eliminate $z_{1}$ to $z_{2}$ by Fourier Motzkin and get a new polyhedron $$C[x_{1,1},\dots,x_{2,m_2},z]'\leq\tilde c.$$

Under what conditions do we have the number of vertices in the new polyhedron $\leq v_1v_2$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Which purpose did it serve to delete and undelete this question several times in a row? -- It certainly does not help you to get good answers. $\endgroup$
    – Stefan Kohl ♦
    Commented Apr 15, 2021 at 9:25
  • $\begingroup$ On vertices following is my thought suppose $x_{1,1},\dots,x_{2,m_2},z$ is a vertex of third polyhedron and $(x_2,z_2)=(x_{2,1},\dots,x_{2,m_2},z_2)$ is a vertex of second polyhedron at some $z_2$ and $(x_1,z_1)=(x_{1,1},\dots,x_{1,m_1},z_1)$ is not a vertex of first polyhedron at any z_1. Now $(x_1,z_1)$ is a convex combination of $m_1+2$ vertex points in first polyhedron by Caratheodory's theorem and by convexity there are two $z_1'$ and $z_1''$ at which $(x_1,z_1')$ and $(x_1,z_1'')$ is on the $m_1$ dimensional face of the first polyhedron. $\endgroup$
    – Turbo
    Commented Apr 15, 2021 at 9:28
  • $\begingroup$ Pick one (say $(x_1,z_1')$) without loss of generality and again by Caratheodory's theorem $(x_1,z_1')$ is a convex combination of $m_1+1$ vertex points on the face containing $(x_1,z_1')$ after projecting the vertices to $z_1'$ in the last coordinate. Now project out the last coordinate and lift to dimension $m_1+m_2+1$ by adding $(x_2,z)$ in the end. This implies $x_{1,1},\dots,x_{2,m_2},z$ is the convex combination of the same $m_1+1$ projected (to $z_1'$) vertex points after lifting to $m_1+m_2+1$ dimensions by adding $(x_2,z)$ in the end. $\endgroup$
    – Turbo
    Commented Apr 15, 2021 at 9:29
  • $\begingroup$ This is impossible if the convex combination is a linear combination of two or more vertices as $x_{1,1},\dots,x_{2,m_2},z$ is a vertex point. Hence there is a $z_1$ satisfying the property $(x_1,z_1)=(x_{1,1},\dots,x_{1,m_1},z_1)$ is a vertex of the first polyhedron. How about $(x_2,z_2)$ and $(x_1,z_1)$ are not vertices in their respective polyhedron? I think $v_1v_2$ holds and I do think above strategy works but not entirely positive. $\endgroup$
    – Turbo
    Commented Apr 15, 2021 at 9:29

0

Reset to default

You must log in to answer this question.