{"id":"arxiv/2609.10330","url":"https://arxiv.org/abs/2609.10330","tags":["math.CO"],"score":0,"title":"The VC-dimension of strongly regular graphs","domain":"math.CO","source":"arxiv","authors":["Isabel Byrne","John Byrne","Sebastian M. Cioabă"],"reviews":0,"subject":"math.CO","summary":"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)=Θ(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}