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
Abstract:
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
Abstract:
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.