# Subspace-evasive set performance in the random case

A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough dimension.

Formally, for parameters $k$ and $\epsilon > 0$, a $(k,c)$-subspace evasive set $S \in \mathbb{F}_q^n$ is such that $|S| > |\mathbb{F}_q^{n}|^{1-\epsilon}$ and $|S \cap H| < c$ for all $k$-dimensional affine subspaces $H \in \mathbb{F}_q^n$.

The goal is to make the intersection $c$ as small as possible.

It is claimed (as trivial in most references) that a random set $S \in \mathbb{F}_q^n$ of size $|\mathbb{F}_q^{n}|^{1-\epsilon}$ has (whp) intersection $c = O(k/\epsilon)$.

Is there a way of showing this? It is supposed to be a simple application of a probabilistic method, but I am stuck and clueless.

For a fixed affine subspace $H$ of dimension $k$, the probability that a random point falls in $H$ is $1/q^{n-k}$. The probability that at least $c$ points in $S$ fall in $H$ is at most: $${q^{(1-\epsilon)n} \choose c} \cdot \frac{1}{q^{(n-k)c}}\leq \frac{q^{(n-\epsilon n) c}}{q^{(n-k)c}} = \frac{1}{q^{(\epsilon n -k)c}}$$ A trivial bound on the number of subspaces of dimension $k$ is $q^{n(k+1)} < q^{2kn}$. So, by the union bound, the probability that there exists a subspace $H$ containing at least $c$ points of $S$ is at most: $$q^{2nk} \cdot \frac{1}{q^{(\epsilon n -k)c}} < 1$$ if $c = 4k/\epsilon$ and $k<\epsilon n/3$.