Evasive Sets, Covering by Subspaces, and Point-Hyperplane Incidences

Given positive integers $$ and a finite field $$ , a set $$ 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 $$ . When k and d are fixed, and c is sufficiently large, the matching lower bound $$ is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of (k, c)-evasive sets in case d is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of k-dimensional linear hyperplanes needed to cover the grid $$ is $$ , which matches the upper bound proved by Balko et al., and settles a problem proposed by Brass et al. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in $$ assuming their incidence graph avoids the complete bipartite graph $$ for some large constant $$ .