Evasive sets, covering by subspaces, and point-hyperplane incidences

Given positive integers $k\leq d$ and a finite field $\mathbb{F}$, a set $S\subset\mathbb{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 |\mathbb{F}|^{d-k}$. When $k$ and $d$ are fixed, and $c$ is sufficiently large, the matching lower bound $Ω(|\mathbb{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}\subset \mathbb{R}^{d}$ is $Ω_{d}\big(n^{\frac{d(d-k)}{d-1}}\big)$, which matches the upper bound proved 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 $\mathbb{R}^{d}$ assuming their incidence graph avoids the complete bipartite graph $K_{c,c}$ for some large constant $c=c(d)$.

No reviews yet.

No comments yet.