Discrete Mathematics and Optimization Seminar

BILL STEIGER
Rutgers University
Monday February 9th at 4.30pm
Burnside 1205



Title. The Convex Hull of Random Hyperplanes.

Abstract. Let $\pi_1,\ldots,\pi_n$ be hyperplanes in general position in $R^d$, let $V=\{\pi_{j_1}\cap\cdots \cap \pi_{j_d}, 1\leq j_1<j_2 < \cdots <j_d\leq n\}$ be the set of vertices, and $N=\vert$conv$(V)\vert$, the number of extreme points of the convex hull of $V$. We show that for $d\leq 3$, if the $\pi_i$ are chosen ``randomly'', there is a constant $c_d>0$ depending on $d$ but not on $n$ so that $E(N)<c_d$. The prospects for $d>3$ will be discussed.