Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Given a combinatorial $d$-polytope $P$ and an orientation on its graph, we may ask the following question: Does there exist a realization of $P\subset \mathbb{R}^d$ and a linear functional $f$ such that $f$ induces the given orientation on the graph of $P$? Holt and Klee introduced a set of necessary conditions on the orientation for it to be a so-called LP-orientation; we show that for cubes, these conditions are very insufficient in the sense that the proportional of Holt-Klee orientations of the $d$-cube which are LP-orientations goes rapidly to 0 as $d$ gets large. For cross-polytopes, we give a strengthening of the Holt-Klee conditions which is both necessary and sufficient for an orientation to be LP.