#
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)

*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**

###
Torsten Ueckerdt - Berlin

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

Posets

*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.

Letzte Aktualisierung:
30.11.2009