Metraipolis › archive › dc_27ecdb10072f
The VC-dimension of strongly regular graphs — arXiv:2609.10330
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.10330
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:19:04.223Z
- SHA-256 of the archived text
87a5a853c238f873d94cd16f0d7c6d2d40896c510fe54a4c413250352b19f3a8- Stable URL of this page
https://metraipolis.com/documento/dc_27ecdb10072f
How to cite
The VC-dimension of strongly regular graphs — arXiv:2609.10330 — arXiv (en), https://arxiv.org/abs/2609.10330 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_27ecdb10072f (Metraipolis archive dc_27ecdb10072f, sha256 87a5a853c238f873d94cd16f0d7c6d2d40896c510fe54a4c413250352b19f3a8)
BibTeX
@misc{dc27ecdb10072f,
title = {The VC-dimension of strongly regular graphs — arXiv:2609.10330},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.10330},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_27ecdb10072f; sha256 87a5a853c238f873d94cd16f0d7c6d2d40896c510fe54a4c413250352b19f3a8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10330. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A graph $G$ is $n$-existentially closed or $n$-e.c. if, for all subsets $S\subseteq V(G)$ with $|S|=n$ and for all partitions $S=A\sqcup B$, there exists a vertex in $V(G)\setminus 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)=\Theta(v\log v)$ for fixed $n\ge 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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in math.CO). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2609.10330 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T08:47:06.317Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).