Combinatorial properties of incompatible systems of linear inequalities and polyhedra

Exact enumeration problems, generating functions (05A15) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Review text

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

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Combinatorial properties of incompatible systems of linear inequalities and polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q923086)