no. 15 · Monday 16 November 2026
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\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^{\min(d-1,\frac{d+k-1}{2})}$. We also show that this exponent is sharp in the $k=d$ case.
- comments
- Simplified proof and stronger main theorem than appeared in first version
- fields
- Combinatorics