Geometric selection theorems

-
Boris Bukh, Princeton University and UCLA
Fine Hall 224

In combinatorial geometry one frequently wants to select a point or a set of points that meets many simplices of a given family. The two examples are choosing a point in many simplices spanned by points of some $P$ in $R^d$, and choosing a small set of points which meets the convex hull of every large subset of $P$ (the weak epsilon-net problem). I will present a new class of constructions that yield the first nontrivial lower bound on the weak epsilon-net problem, and improve the best bounds for several other selection problems. Joint work with Jiří Matoušek and Gabriel Nivasch.