VC-dimension of distance graphs in finite field geometries

Abstract

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