Return to Colloquia & Seminar listing
Linear Programming orientations of Polyhedra
Algebra & Discrete Mathematics| Speaker: | Mike Develin, UC Berkeley |
| Location: | 693 Kerr |
| Start time: | Thu, Oct 31 2002, 12:10PM |
Description
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.