VC-dimension and pseudo-random graphs

Abstract

Let $G$ be a graph and $U\subset V(G)$ be a set of vertices. For each $v\in U$, let $h_v:U\to \{0,1\}$ be the function defined by \[h_v(u)=\begin{cases} &1 ~\mbox{if}~u\sim v, u\in U\\&0 ~\mbox{if}~u\not\sim v, u\in U\end{cases},\] and set $\mathcal{H}(U):=\{h_v:v\in U\}$. The first purpose of this paper is to study the following question: What families of graphs $G$ and what conditions on $U$ do we need so that the VC-dimension of $\mathcal{H}(U)$ can be determined? We show that if $G$ is a pseudo-random graph, then under some mild conditions, the VC dimension of $\mathcal{H}(U)$ can be bounded from below. Specific cases of this theorem recover and improve previous results on VC-dimension of functions defined by the well-studied distance and dot-product graphs over a finite field.