Paperlane

no. 15 · Monday 16 November 2026

VC-dimension of distance graphs in finite field geometries

Brian McDonald Bakas, Moustapha Diallo and Alex McDonald

math.CO · v2

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
pdf ↗ page arXiv:2609.32052 ↗