Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, June 10, 2014, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Zuzana Safernová (Charles University)

Bounds for Pach's selection theorem

We focus on the estimates on the selection constant in the following geometric selection theorem by Pach: For every positive integer d there is a constant cd > 0 such that whenever X1, … , Xd+1 are n-element subsets of Rd, then we can find a point p in Rd and subsets Yi ⊂ Xi  for every i=1,…, d+1, each of size at least cd n, such that p belongs to all rainbow d-simplices determined by Y1, … , Yd+1, that is, simplices with one vertex in each Yi.

We will discuss a lower and upper bound for the constant cd, more concretely, 2-2^{d^2 + O(d)} ≤ cd ≤ 0.9975d. In order to show the upper bound, we prove the fact that the minimum solid angle of every d-simplex is exponentially small.

Joint work with Honza Kynčl, Pavel Paták and Martin Tancer.

Information for students and suggested topics for student talks