LPorientations of cubes and crosspolytopesMike DevelinUC Berkeley
February 21,

ABSTRACT


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 socalled LPorientations. Chief among these is the HoltKlee condition, which states that on every $k$dimensional face of a polytope an LPorientation contains at least $k$ vertexdisjoint paths from source to sink. We will investigate the case of cubes and crosspolytopes, showing that the percentage of HoltKlee orientations of the $n$cube which are LP goes to 0 as $n$ goes to infinity. No prior knowledge of polytopes or LPorientations will be assumed. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

