• Calendar

January 11, Wednesday
12:00 – 13:00

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)/(k+d+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.