On 04.05.2017 at 12:20 in S6, there is the following noon lecture:
Covering lattice points by subspaces and counting point-hyperplane incidences
(joint work with J. Cibulka and P. Valtr)
Let d and k be integers with 1 <= k <= d-1. Let Lambda be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in the intersection of Lambda with K.
In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional n x ... x n grid is at least Omega(n^(d(d-k)/(d-1)-epsilon)) and at most O(n^(d(d-k)/(d-1))), where epsilon > 0 is an arbitrarily small constant. This nearly settles a problem mentioned in the book of Brass, Moser, and Pach.
We also find tight bounds for the minimum number of k-dimensional affine subspaces needed to cover the intersection of Lambda and K. We use these new results to improve the best known lower bounds for the maximum number of point-hyperplane incidences by Brass and Knauer.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010