Evasive sets, twisted varieties, and container-clique trees
Abstract
In the affine space over the finite field of order , a point set is said to be -evasive if the intersection between and any variety, of dimension and degree at most , has cardinality less than . As tends to infinity, the size of a -evasive set in is at most by a simple averaging argument. We exhibit the existence of such evasive sets of sizes at least for much smaller values of than previously known constructions, and establish an enumerative upper bound for the total number of such evasive sets. The existence result is based on our study of twisted varieties. In the projective space over an algebraically closed field, a variety is said to be -twisted if the intersection between and any variety of dimension and degree at most has dimension zero. We prove an upper bound on the smallest possible degree of twisted varieties which is best possible in a mild sense. The enumeration result includes a new technique for the container method which we believe is of independent interest. To illustrate the potential of this technique, we give a simpler proof of a result by Chen–Liu–Nie–Zeng that characterizes the maximum size of a collinear-triple-free subset in a random sampling of up to polylogarithmic factors.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on1
Related papers
- A New Lower Bound on Hadwiger-Debrunner Numbers in the PlaneChaya Keller, Shakhar SmorodinskySODA 2020 · 4 citations
- Halving by a Thousand Cuts or PuncturesSariel Har-Peled, Da Wei ZhengSODA 2023
- Stronger bounds for weak epsilon-nets in higher dimensionsNatan RubinSTOC 2021 · 1 citation
- Proximity Gaps for Reed-Solomon CodesEli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty et al.FOCS 2020 · 58 citations
- Helly-Type Theorems for Splitting Point SetsLidor Portal, Natan RubinSODA 2026
