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 &gt; 0$, a $(k,c)$-subspace evasive set $S \in \mathbb{F}_q^n$ is such that $|S| &gt; |\mathbb{F}_q^{n}|^{1-\epsilon}$ and $|S \cap H| &lt; 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.
Here's a quick calculation.

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)} &lt; 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}} &lt; 1$$
if $c = 4k/\epsilon$ and $k&lt;\epsilon n/3$.