Speaker: Gabriel Nivasch (EPFL Lausanne)
 
Title: Upper bounds for centerflats
 
Abstract:
 
For every fixed d and every n, we construct an n-point set G in R^d 
such that every line in R^d is contained in a halfspace that contains 
only 2n/(d+2) points of G (up to lower-order terms).
 
Apparently, the point set G satisfies the following more general property: 
For every k, every k-flat in R^d is contained in a halfspace that contains 
only (k+1) n / (d+k+1) points of G (up to lower-order terms).
 
In 2008, Bukh, Matousek, and Nivasch conjectured the following generalization 
of Rado's centerpoint theorem: For every n-point set S in R^d and every k, 
there exists a k-flat f in R^d such that every halfspace that contains f 
contains at least (k+1) n / (d+k+1) points of S (up to lower-order terms). 
(The centerpoint theorem is obtained by setting k=0.) Such a flat f would 
be called a "centerflat".
 
Thus, our upper bound construction shows that the leading constant (k+1)/(d+k+1) 
in the above conjecture is tight (certainly for k = 1, and apparently for all k).
 
The set G of our construction is the "stretched grid" -- a point set which 
has been previously used by Bukh et al. for other related purposes.
 
Joint work with Boris Bukh.