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

Given positive integers and a finite field , a set is (, )- if every -dimensional affine subspace contains at most elements of . By a simple averaging argument, the maximum size of a (, )-subspace evasive set is at most . When and are fixed, and 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 (, )-evasive sets in case 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 -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 .