Abstract
Given positive integers k ≤ d and a finite field F , a set S ⊂ Fd 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 ⊂ Rd is Ωd(n1/) , 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 Rd assuming their incidence graph avoids the complete bipartite graph Kc,c for some large constant c = c(d) .