The VC-dimension of strongly regular graphs

@misc{byrne2026vcdimension,
  title = {{The VC-dimension of strongly regular graphs}},
  author = {Isabel Byrne and John Byrne and Sebastian M. Cioabă},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.10330},
  eprint = {2609.10330},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10330},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - The VC-dimension of strongly regular graphs
AU  - Isabel Byrne
AU  - John Byrne
AU  - Sebastian M. Cioabă
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2609.10330
UR  - https://arxiv.org/abs/2609.10330
AB  - A graph G is n-existentially closed or n-e.c. if, for all subsets S⊆ V(G) with |S|=n and for all partitions S=Asqcup B, there exists a vertex in V(G)∖ S adjacent to all vertices in A and no vertices in B. We study the minimum number of edges m(v,n) of a v-vertex n-e.c. graph, and show that m(v,2)=3v+O(1) while m(v,n)=Θ(vlog v) for fixed n≥ 3. The latter result uses a connection to binary covering arrays. A related parameter is the VC-dimension of G, defined as the size of the largest subset of vertices shattered by the neighborhoods of vertices in G. We initiate systematic study of the VC-dimensions of strongly regular graphs (SRGs). We characterize the sufficiently large SRGs with VC-dimension 2. Furthermore, we determine the VC-dimension of sufficiently large Latin square graphs and of all SRGs of order at most 28, and prove upper bounds for SRGs arising from orthogonal arrays or Steiner systems.
ER  -