Evasive sets, twisted varieties, and container-clique trees

In the affine space \(\mathbb{F}_q^n\) over the finite field of order \(q\), a point set \(S\) is said to be \((d,k,r)\)-evasive if the intersection between \(S\) and any variety, of dimension \(k\) and degree at most \(d\), has cardinality less than \(r\). As \(q\) tends to infinity, the size of a \((d,k,r)\)-evasive set in \(\mathbb{F}_q^n\) is at most \(O(q^{n-k})\) by a simple averaging argument. We exhibit the existence of such evasive sets of sizes at least \(\Omega(q^{n-k})\) for much smaller values of \(r\) than previously known constructions, and establish an enumerative upper bound \(2^{O(q^{n-k})}\) for the total number of such evasive sets. The existence result is based on our study of twisted varieties. In the projective space \(\mathbb{P}^n\) over an algebraically closed field, a variety \(V\) is said to be \(d\)-twisted if the intersection between \(V\) and any variety of dimension \(n-\dim(V)\) and degree at most \(d\) 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 \(\mathbb{F}_q^2\) up to polylogarithmic factors.