Benny Sudakov: Evasive sets, covering by subspaces, and point-hyperplane incidences

Given positive integers $k\le d$ and a finite field $F$, a set $S\subset F^d$ is $(k,c)$-subspace evasive if every $k$-dimensional affine subspace contains at most $c$ elements of $S$. By a simple averaging argument, the maximum size of a $(k,c)$-subspace evasive set is at most $c|F{|}^{d-k}$. In this talk we discuss the construction of evasive sets, matching this bound. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. Using it we determine the minimum number of $k$-dimensional linear hyperplanes needed to cover the grid $[n{]}^d$. This extends the work by Balko, Cibulka, and Valtr, and settles a problem proposed by Brass, Moser, and Pach. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in dimension $d$ assuming their incidence graph avoids the complete bipartite graph $K_{t,t}$ for some large constant $t=t\left(d\right)$. Joint work with Istvan Tomon.