# Noon lecture

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

On 4.5.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 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page