Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

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

Martin Balko

Abstract

(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.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010