שלחו לחבר

One-sided epsilon-approximants

Seminar
Speaker
Gabriel Nivasch (Ariel University)
Date
29/05/2016 - 15:30 - 14:00
Place
Math building, 3rd floor seminar room (216/201)
Abstract

We introduce the notion of "one-sided epsilon-approximants", which is in strength between epsilon-nets and usual (two-sided) epsilon-approximants. Given an n-point set P in R^d, a one-sided epsilon-approximant for P (with respect to convex sets) is a multiset A such that, for every convex set C, we have |P cap C|/|P| - |A cap C|/|A| <= epsilon.

We show that, in contrast with the usual epsilon-approximants, every P has a one-sided epsilon-approximant with respect to convex sets of size g(eps, d) for some g, but independent of n.

Unfortunately, due to the use of a geometric Ramsey theorem, our bound is very weak: g(eps, d) <= 2^2^...^2^(1/epsilon)^c, with d-1 2's.

For more info, see arXiv:1603.05717

Joint work with Boris Bukh.

תאריך עדכון אחרון : 18/05/2016