VC-dimension and pseudo-random graphs

Let $G$ be a graph and $U\subset V(G)$ be a set of vertices. For each $v\in U$, let $h_v\text{\hspace{0.17em}⁣}:U\to \{0,1\}$ be the function defined by $$h_v(u)=\{\begin{array}{ll}& 1ifu\sim v,u\in U\\ & 0ifu\sim ̸v,u\in U\end{array},$$ and set $\mathcal{H}(U):=\{h_v\text{\hspace{0.17em}⁣}: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.