VC-dimension of distance graphs in finite field geometries
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.32052
curl -X POST /api/v1/records/arxiv/2609.32052/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.32052/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'