Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 47 min ago
PreprintarXiv licencearXiv

VC-dimension of distance graphs in finite field geometries

  • Brian McDonald Bakas
  • Moustapha Diallo
  • Alex McDonald
Open at sourcePDFDOICite

Abstract

We study the VC-dimension of distance graphs of large subsets of vector spaces over finite fields. For 3≤ k≤ d, we prove the distance graph of E⊂ Fqd has VC-dimension at least k provided that |E|>Cqd−⌊ (d−k)/3⌋−1. We also show that this exponent is sharp in the k=d case.

Related

  1. Default-Distance Entropy and Metric Dimension in Finite Geometries
    Maximiliano Vazquez
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Optimality of finite field dimension expanders
    Urban Jezernik, Markus Reineke
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryProbabilityarXiv
  3. Distances in the collinearity graphs of geometries related to simplex codes
    Adam Tyc
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. φ-FD, a second order finite difference scheme for geometries defined by a level-set function: the Neumann case *
    Michel Duprez, Vanessa Lleras, Alexei Lozinski +2
    HALPreprintCC BY 4.0Full textAnalysis & PDEsNumerical analysis & scientific computingHAL
  5. phi-FD, a second order finite difference scheme for geometries defined by a level-set function: the Neumann case
    Michel Duprez, Vanessa Lleras, Alexei Lozinski +2
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv

Cite

BibTeXRIS
BibTeX
@misc{bakas2026vcdimension,
  title = {{VC-dimension of distance graphs in finite field geometries}},
  author = {Brian McDonald Bakas and Moustapha Diallo and Alex McDonald},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.32052},
  eprint = {2609.32052},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.32052},
}
RIS
TY  - UNPB
TI  - VC-dimension of distance graphs in finite field geometries
AU  - Brian McDonald Bakas
AU  - Moustapha Diallo
AU  - Alex McDonald
PY  - 2026
DA  - 2026/09/25
PB  - arXiv
DO  - 10.48550/arxiv.2609.32052
UR  - https://arxiv.org/abs/2609.32052
AB  - We study the VC-dimension of distance graphs of large subsets of vector spaces over finite fields. For 3≤ k≤ d, we prove the distance graph of E⊂ F_q^d has VC-dimension at least k provided that |E|>Cq^d−⌊ (d−k)/3⌋−1. We also show that this exponent is sharp in the k=d case.
ER  -