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

Given positive integers k ≤ d and a finite field F , a set S ⊂ 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 . When k and d are fixed, and c is sufficiently large, the matching lower bound Ω (| F | d - k) 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 [ n ] d ⊂ R d is Ω d (n d (d - k) d - 1 ) , 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 R d assuming their incidence graph avoids the complete bipartite graph K c , c for some large constant c = c (d) . [ABSTRACT FROM AUTHOR]