Jiri Matousek: 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.