Monday, December 14 , 2009
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041
Lecture - 14:15
A set N in the d-dimensional Euclidean space is called a weak epsilon-net (with respect to convex set) for a finite set X if every convex set containing at least an epsilon-fraction of the points of X intersects N. It is known that weak epsilon-nets exist for every X, of size depending only on d and epsilon, but the quantitative dependence remains a mystery. We establish superlinear lower bounds in terms of epsilon, for every d fixed, d>1. The proof relies on "stretched grids", products of sets with very fast-growing coordinates. The problem is first translated to epsilon-nets for stair-convex sets, where stair-convexity is an analog of convexity but with a much more combinatorial nature. Then an argument resembling Roth's classical lower bound in discrepancy theory yields the lower bound. The use of stretched grids appears as a generally useful method for combinatorial problems involving convexity.
Colloquium - 16:00
After introducing the concept of alpha-orientations, I will expose how they can be encoded by the downsets of a corresponding partially ordered set. Hence we attempt to enumerate all alpha-orientations by enumerating downsets. I will sketch the currently best-known methods for this problem and argue how they can be improved.