Combinatorial properties of incompatible systems of linear inequalities and polyhedra (Q923086)

The notion of a diagonal of a convex polytope is introduced. Some relations between maximal compatible subsystems of the incompatible system (1) \((a_ i,x)>0,\quad a_ i,x\in {\mathbb{R}}^ n,\quad i\in M=\{1,...,m\}\) of linear inequalities and diagonals of a polytope are established. Let B be a finite set in the space \({\mathbb{R}}^ n\). A subset A of B such that \(conv A\cap ri conv B\neq \emptyset\) and is minimal with respect to this property is called a diagonal of B. In the case \(B=vert conv B\) this is the definition of a diagonal of the convex polytope conv B. The main result is contained in the following theorem. Let \(B=(b_ 1,b_ 2,...,b_ m)\) be the Gale transform of the set \(A=(a_ 1,a_ 2,...,a_ m),\quad d=m-n-1,\) and \(pos\{a_ 1,...,a_ m\}={\mathbb{R}}^ n.\) The subset \(L\subseteq M=\{1,2,...,m\}\) is the set of indices of a maximal compatible subsystem of the system (1) if and only if \(M\setminus L\) is the set of indices of some diagonal of B. As a consequence, the author obtains the following formula for the number \({\mathcal D}(d,m)\) of diagonals of the cyclic d-polytope with m vertices: \({\mathcal D}(d,m)=1\) if \(m\leq d+1,\quad {\mathcal D}(d,m)=2\left( \begin{matrix} m-k-2\\ k\end{matrix} \right)+\left( \begin{matrix} m-k-2\\ k+1\end{matrix} \right)\) if \(m\geq d+2\) and \(d=2k,\quad {\mathcal D}(d,m)=\left( \begin{matrix} m-k-2\\ k+1\end{matrix} \right)+\left( \begin{matrix} m-k-3\\ k\end{matrix} \right)\) if \(m\geq d+2\) and \(d=2k+1\).