{"id":"arxiv/2609.32052","url":"https://arxiv.org/abs/2609.32052","tags":["math.CO"],"score":0,"title":"VC-dimension of distance graphs in finite field geometries","domain":"math.CO","source":"arxiv","authors":["Brian McDonald Bakas","Moustapha Diallo","Alex McDonald"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}