January 19, Wednesday 14:15, Jacobs Building Room 303

Title: Stabbing Simplices and Convex Sets

Lecturer : Gabriel Nivasch

Lecturer homepage : http://people.inf.ethz.ch/gnivasch/index.html

Affiliation : ETH Zurich


The "First Selection Lemma" states that for every n-point set S in R^d there exists a point x in R^d that intersects at least a constant fraction of the (n choose (d+1)) d-dimensional simplices spanned by S. The question is, what is the maximum value of this constant.

We provide an upper bound by constructing a specific set S for which no point x in R^d intersects more than (n/(d+1))^(d+1) simplices. Our construction is what might be called a "point set in stretched position"; by having the coordinates of the points form a rapidly-increasing sequence, containment relations between points and simplices can be expressed in purely combinatorial terms.
Our "point set in stretched position" also yields an interesting lower bound for "weak epsilon-nets", involving the inverse-Ackermann function.
Joint work with Boris Bukh and Jiri Matousek.