论文标题
回避集，由子空间覆盖和点hyperplane事件
Evasive sets, covering by subspaces, and point-hyperplane incidences
论文作者
论文摘要
给定积极整数$ k \ leq d $和有限的字段$ \ mathbb {f} $，一个$ s \ subset \ subset \ mathbb {f}^{d} $是$（k，c）$ - 如果每个$ k $ k $ dimensional coldine coldpace cop of yoss $ c $ c $ s $ s $ s $ s $ s $ s $ s $ s。通过简单的平均参数，$（k，c）$ - 子空间回避集的最大大小最多是$ c | \ mathbb {f} |^{d-k} $。当$ k $和$ d $固定并且$ c $足够大时，匹配的下限$ω（| \ m马理{f} |^{d-k}）$由dvir和lovett证明。我们使用随机代数法提供了该结果的替代证明。我们还证明，如果$ d $较大，则在$（k，c）$的大小上的急剧上限，这是Ben-Aroya和Shinkar的扩展结果。 最佳回避集的存在在组合几何形状中有几个有趣的后果。我们表明，覆盖网格$ [n]^{n]^{d} \ subset \ mathbb {r}^{d} $的最低数量是$ k $二维线性超平面，是$ω__{d} \ big（n^n^^{ Cibulka和Valtr，解决了铜管，Moser和Pach提出的问题。此外，我们在$ \ Mathbb {r}^{d} $中提高了点和超级平面之间的最大发病率的最大发病率数量，假设其发射率图避免了某些大常数$ c = c（d）$。
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)$.
