LP-orientations of cubes and crosspolytopes

Mike Develin

UC Berkeley

February 21,
refreshments at 3:45pm


Given a polytope $P\subset\mathbb{R}^d$ and a generic linear functional $f$, we can describe an orientation of the graph of $P$ by orienting each edge towards the vertex on which $f$ is larger. We will survey the known results on so-called LP-orientations. Chief among these is the Holt-Klee condition, which states that on every $k$-dimensional face of a polytope an LP-orientation contains at least $k$ vertex-disjoint paths from source to sink. We will investigate the case of cubes and cross-polytopes, showing that the percentage of Holt-Klee orientations of the $n$-cube which are LP goes to 0 as $n$ goes to infinity.

No prior knowledge of polytopes or LP-orientations will be assumed.

Speaker's Contact Info: develin(at-sign)math.berkeley.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on February 03, 2003 at 05:02 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.