VC-dimension of distance graphs in finite field geometries

Source abstract

We study the VC-dimension of distance graphs of large subsets of vector spaces over finite fields. For $3\leq k\leq d$, we prove the distance graph of $E\subset \F_q^d$ has VC-dimension at least $k$ provided that $|E|>Cq^{d-\lfloor \frac{d-k}{3}\rfloor-1}$. We also show that this exponent is sharp in the $k=d$ case.