Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Jiri Matousek - Prag

Stair-convexity and lower bounds for weak epsilon-nets
(joint work with Boris Bukh and Gabriel Nivasch)

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

Torsten Ueckerdt - Berlin

Enumerating All: alpha-Orientations of Planar Graphs and Downsets of

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.

Letzte Aktualisierung: 30.11.2009