# VC-dimension and pseudo-random graphs

Thang Pham University of Science, Vietnam National University, Hanoi. Email:
<EMAIL_ADDRESS>Steven Senger Department of Mathematics, Missouri
State University. Email<EMAIL_ADDRESS>Michael Tait
Department of Mathematics and Statistics, Villanova University. Email:
<EMAIL_ADDRESS>Nguyen Thu-Huyen Fulbright University Vietnam.
Email<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a graph and $U\subset V(G)$ be a set of vertices. For each $v\in
U$, let $h_{v}\colon 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}\colon 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.

##  1 Introduction

In this paper, we study the VC-dimension of sets of functions that are defined
by graph adjacency. We start with the requisite definitions.

######  Definition 1.1.

Let $\mathcal{H}$ be a collection of functions from $V$ to $\\{0,1\\}$. We say
that $\mathcal{H}$ shatters a finite set $X\subset V$ if the restriction of
$\mathcal{H}$ to $X$ yields every possible function from $X$ to $\\{0,1\\}$.

######  Definition 1.2.

Let $\mathcal{H}$ be a collection of functions from $V$ to $\\{0,1\\}$. The
Vapnik-Chervonenkis dimension (in short, VC-dimension) of $\mathcal{H}$ is $d$
if any only if there exists a set $X\subset V$ of size $d$ that is shattered
by $\mathcal{H}$, and no subset of $X$ of size $d+1$ is shattered by
$\mathcal{H}$.

It is mentioned in the book [9] that “the VC-dimension can be determined
without great difficulty in several simple cases, such as for half-spaces or
balls in $\mathbb{R}^{d}$, but for only slightly more complicated families its
computation becomes challenging.” Before stating our main results, we need to
set up notation as follows.

Let $G=(V,E)$ be a graph with the vertex set $V$ and the edge set $E$. For two
vertices $u,v\in V$, by $u\sim v$, we mean there is an edge between $u$ and
$v$.

Let $U\subset V$ be a set of vertices. For each $v\in U$, let $h_{v}\colon
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}\colon v\in U\\}.$

The following question appears to us to be natural and fundamental.

######  Question 1.3.

For which families of graphs and under what conditions on $U$ can we determine
the VC-dimension of $\mathcal{H}(U)$?

One of the primary motivations for this question comes from a series of recent
papers [2, 4, 6, 10] in which the authors studied graphs $G$ with
$V(G)=\mathbb{F}_{q}^{t}$, where $\mathbb{F}_{q}$ is the finite field of order
$q$, and there is an edge between two vertices $x$ and $y$ if $P(x,y)=1$ for
some polynomials $P$. More precisely, if $t=2$ and
$P(x,y)=(x_{1}-y_{1})^{2}+(x_{2}-y_{2})^{2}$, then Fitzpatrick, Iosevich,
McDonald, and Wyman [4] showed that for any subset
$U\subset\mathbb{F}_{q}^{2}$ of size at least $Cq^{15/8}$, the set
$\mathcal{H}(U)$ has VC-dimension equal to $3$. They also showed that for
$|U|\geq Cq^{3/2}$ the set $\mathcal{H}(U)$ has VC-dimension at least $2$.
They asked specifically about the gap between these two exponents and if one
can determine the VC-dimension for sets of size $o(q^{15/8})$. When $t=3$ and
$P(x,y)=x_{1}y_{1}+x_{2}y_{2}+x_{3}y_{3}$, Iosevich, McDonald, and Sun [6]
showed that in this graph any subset $U\subset\mathbb{F}_{q}^{3}$ of size at
least $Cq^{11/4}$ has the property that $\mathcal{H}(U)$ has VC-dimension
equal to $3$, and that any set with $|U|\geq Cq^{5/2}$ has VC-dimension at
least $2$. They similarly remarked that they “do not know to what extent the
exponent $\frac{11}{4}$… and … $\frac{5}{2}$ are sharp, but we know that
neither exponent can fall below $2$.” Our main goal in this paper is to
develop a framework for these questions. Ideally, we would like to be able to
prove theorems like the concrete examples given above as specific applications
of a general theorem. We make partial progress towards this goal. More
precisely, we will address Question 1.3 for $(n,d,\lambda)$-graphs, i.e.
graphs with $n$ vertices, regular of degree $d$, and the second largest
eigenvalue is at most $\lambda$ in absolute value. Our main results can be
stated as follows.

######  Theorem 1.4.

Let $G$ be an $(n,d,\lambda)$-graph with $d=o(n)$. Let $U$ be a vertex set.
Assume that $\lambda n/d=o(|U|)$, then the VC-dimension of $\mathcal{H}(U)$ is
at least $2$.

If more conditions are allowed, then one can be guaranteed a larger dimension
in the next theorem. Although in the next theorem the dimension is increasing
by only one from Theorem 1.4, the proof becomes much more difficult.

######  Theorem 1.5.

Let $G$ be an $(n,d,\lambda)$-graph with $d=o(n)$. Let $U$ be a vertex set.
Assume that the following properties hold.

  1. 1.

Given any three vertices $v_{1},v_{2},v_{3}\in U$, we can find three vertices
$u_{1},u_{2},u_{3}\in U$ such that $u_{i}\sim v_{j}$ if and only if $i=j$,

  2. 2.

The size of $U$ satisfies

$|U|\geq C\max\left\\{\lambda^{2/3}(n/d)^{2},\lambda(n/d)^{13/7}\right\\}.$

where $C$ is an absolute constant. Then the VC-dimension of $\mathcal{H}(U)$
is at least $3$.

We make some remarks before proceeding. First, since $|\mathcal{H}(U)|=|U|$,
the trivial upper bound gives that the VC-dimension is at most
$\log_{2}(|U|)$, and sets with VC-dimension $2$ or $3$ are far from this.
Second, when showing that the VC-dimension of a set is at least $3$, we
require condition 1 in the hypotheses of Theorem 1.5. It would be very
interesting to get rid of this condition or replace it with a more natural one
that applies to $(n,d,\lambda)$-graphs in a more general way. Finally, in all
of the previously studied graphs defined by distances or dot-products, there
are geometric reasons that make finding a corresponding upper bound on the VC-
dimension easy. We do not know how to give upper bounds on VC-dimension in a
general way for $(n,d,\lambda)$-graphs.

The main idea to prove Theorems 1.4 and 1.5 is to find a subset of $2$ or $3$
vertices respectively that are shattered by a large enough subset $U$. From
the way the functions are defined, we must find sets of vertices with
prescribed adjacencies and non-adjacencies; the backbone of our proof will be
to show that in a suitably large subset of a pseudo-random graph, we can find
and count various subgraphs. We find these results interesting in their own
right, as finding or counting certain subgraphs in pseudo-random graphs has a
long history of study. For example, a representative result is the following
classical theorem of Alon [7, Theorem 4.10].

######  Theorem 1.6.

Let $H$ be a fixed graph with $r$ edges, $s$ vertices and maximum degree
$\Delta$, and let $G$ be an $(n,d,\lambda)$-graph with $d\leq 0.9n$. Then for
any subset $U$ with $\lambda\left(\frac{n}{d}\right)^{\Delta}=o(|U|)$, the
number of copies of $H$ in $U$ is

$(1+o(1))\frac{|U|^{s}}{|Aut(H)|}\left(\frac{d}{n}\right)^{r}$

We will state our subgraph counting theorems in the coming sections and give
some discussion of them, including comparison with Theorem 1.6, in Section 3.
Instead of counting subgraphs exactly, it will be more useful for us to
instead count homomorphisms from a graph $H$ to the graph induced by a subset
of vertices $U$ in our graph. Given a subset of vertices $U\subset V(G)$ and a
fixed subgraph $H$, we will use the notation $H(U)$ to denote the number of
homomorphisms from $H$ to the induced subgraph $G[U]$. For example, if $H$ is
a cycle on $k$ vertices, then $C_{k}(U)$ denotes the number of sequences of
vertices $\\{v_{1},\cdots,v_{k}\\}$ such that $v_{i}\in U$ and $v_{i}\sim
v_{i+1}$ for $1\leq i\leq k-1$ and $v_{i}\sim v_{k}$. Notice that this is
counting labeled and possibly degenerate cycles.

###  1.1 Applications

We now present some applications of Theorems 1.4 and 1.5. There are many
$(n,d,\lambda)$-graphs that can be computed explicitly in the literature, such
as Cayley graphs. In this section, we only emphasize some particular ones,
viz., dot-product graphs and distance graphs.

Let $G=(V,E)$ be the dot-product graph in $\mathbb{F}_{q}^{t}$ defined by
$V=\mathbb{F}_{q}^{t}\setminus(0,\ldots,0)$, and there is an edge between two
vertices $(x_{1},x_{2},\ldots,x_{t})$ and $(y_{1},y_{2},\ldots,y_{t})$ if
$x_{1}y_{1}+\cdots+x_{t}y_{t}=1$. It is well-known in the literature that this
graph is an $(n,{d},\lambda)$-graph with $n=q^{t}-1$, $d\sim q^{t-1}$ and
$\lambda\leq 2q^{\frac{t-1}{2}}$, see [12, Theorem 8.1] for example.

The following is the direct application of Theorems 1.4 and 1.5.

######  Theorem 1.7.

Let $U\subset\mathbb{F}_{q}^{t}$ be a subset of vertices in the dot-product
graph. There is a constant $C$ such that

  1. 1.

If $|U|\geq Cq^{\frac{t+1}{2}}$, then the dimension of $\mathcal{H}(U)$ is at
least $2$.

  2. 2.

If $|U|\geq C\max\\{q^{\frac{7t+19}{14}},q^{t-1}\\}$, then the dimension of
$\mathcal{H}(U)$ is at least $3$.

In three dimensions, if the geometric properties are taken into consideration,
then we have a better result, which improves earlier results in [6].

######  Theorem 1.8.

Let $U\subset\mathbb{F}_{q}^{3}$ be a subset of vertices in the dot-product
graph. There is a constant $C$ such that

  1. 1.

If $|U|\geq Cq^{2}$, then the dimension of $\mathcal{H}(U)$ is at least $2$.

  2. 2.

If $|U|\geq Cq^{5/2}$, then the dimension of $\mathcal{H}(U)$ is equal to $3$.

This theorem recovers the exponent $3/2$ in dimension $2$ from the paper [6]
and improves the exponent $11/4$ in dimension 3 from [6] down to $5/2$.

We now move to the graph defined by the distance function. Let $G=(V,E)$ be
the distance graph in $\mathbb{F}_{q}^{t}$ defined by $V=\mathbb{F}_{q}^{t}$,
and there is an edge between two vertices $(x_{1},x_{2},\ldots,x_{t})$ and
$(y_{1},y_{2},\ldots,y_{t})$ if
$(x_{1}-y_{1})^{2}+\cdots+(x_{t}-y_{t})^{2}=1$. It is well-known in the
literature that this graph is an $(n,{d},\lambda)$-graph with $n=q^{t}$,
$d\sim q^{t-1}$, $\lambda\leq 2q^{\frac{t-1}{2}}$-graph, see [3, Sections 2–6]
and [8, Section 3] for example. As above, we also have the following
application in this setting.

######  Theorem 1.9.

Let $U\subset\mathbb{F}_{q}^{t}$ be a subset of vertices in the distance
graph. There is a constant $C$ such that

  1. 1.

If $|U|\geq Cq^{\frac{t+1}{2}}$, then the dimension of $\mathcal{H}(U)$ is at
least $2$.

  2. 2.

If $|U|\geq C\max\\{q^{\frac{7t+19}{14}},q^{t-1}\\}$, then the dimension of
$\mathcal{H}(U)$ is at least $3$.

Compared to the result in [4] with $t=2$, we recover their result to find VC-
dimension $2$ but we can see that we get a trivial result for VC-dimension $3$
whereas in [4] the exponent $15/8$ was given. This comes from the fact that in
some specific settings, counting subgraph configurations in the next sections
is unnecessary, and in the plane $\mathbb{F}_{q}^{2}$, the distance graph
possesses some nice geometric properties, which implies a simpler proof with
better exponents. Unlike the dot-product graph, we do not know how to improve
the exponent $15/8$, which is left as an open question.

###  1.2 Open questions

We do not believe that Theorem 1.5 is sharp in general. In particular, one of
our estimates on subconfigurations (Theorem 3.2 below) involves a recursive
step using Cauchy-Schwarz that could probably be improved in many cases, but
this was the best estimate we found. In Section 3 we point out other
configurations for which we believe it would be interesting to tighten our
estimates.

Our theorems give conditions to guarantee that the VC-dimension of an
$(n,d,\lambda)$-graph is at least 2 or 3. In [1], for each fixed $D$ the
authors give the threshold function for a random graph to have VC-dimension at
least $D$. It would be interesting to do this in the setting of
$(n,d,\lambda)$-graphs: that is, to give conditions on $d$ and $\lambda$ which
would guarantee that the graph has VC-dimension at least $D$. New ideas would
be needed to do this. Already to show a lower bound of VC-dimension $4$ using
the techniques in this paper is outside of our capabilities.

Finally, in Theorem 1.8, we do not have a construction showing that the
exponent $5/2$ is best possible, but we believe that it could be, and it would
be interesting to determine if this is correct.

###  1.3 Structure

The paper is organized as follows. In Section 2 we collect preliminary lemmas
that we will require during the proofs. In Section 3 we show that we can count
or bound $H(U)$ for various graphs $H$ as long as $U$ is large enough. In
Sections 4 and 5, we show how to use these counting results to prove Theorems
1.4 and 1.5. Finally, in Section 6, we show our applications to the distance
and dot-product graphs. Given two functions $f,g:\mathbb{N}\to\mathbb{N}$ we
will use the notation $f\ll g$ to mean that $f=O(g)$ and $f\gg g$ to mean that
$f=\Omega(g)$.

##  2 Tools

In this section we list the tools that we will need in our proofs. We will
extensively use the following weighted version of the expander mixing lemma.
As a historical note, the (unweighted) expander mixing lemma was proved at
least as early as 1980 by Haemers in his PhD thesis ([5] Theorem 3.1.1) in the
language of design theory.

######  Lemma 2.1.

Let $G=(V,E)$ be an $(n,d,\lambda)$-graph, and $A$ be its adjacency matrix.
For real $f,g\in L^{2}(V)$, we have

$\left|\langle f,Ag\rangle-
dn\mathbb{E}(f)\mathbb{E}(g)\right|\leq\lambda\|f\|_{2}\|g\|_{2},$

where

$\mathbb{E}(f):=\frac{1}{n}\sum_{v\in V}f(v),\text{ and
}||f||_{2}^{2}=\sum_{v\in V}|f(v)|^{2}.$

At times, the classical expander mixing lemma will not be precise enough for
our purposes. We will use the following lemma, first proved in [11], that is
specific to tensor powers of graphs. Notice that the function $f$ below has a
different domain than $f$ above.

######  Proposition 2.2.

Let $G$ be an $(n,d,\lambda)$-graph. For two non-negative functions $f,g\colon
V\times V\to\mathbb{R}$, we define $F(x)=\sum_{y}f(x,y)$,
$G(z)=\sum_{w}g(z,w)$, $F^{\prime}(y)=\sum_{x}f(x,y)$, and
$G^{\prime}(w)=\sum_{z}g(z,w)$. Then we have

$\left|\sum_{x\sim z,y\sim
w}f(x,y)g(z,w)-\frac{d^{2}}{n^{2}}||f||_{1}||g||_{1}\right|\leq\lambda^{2}||f||_{2}||g||_{2}+\frac{d\lambda}{n}\left(||F||_{2}||G||_{2}+||F^{\prime}||_{2}||G^{\prime}||_{2}\right).$

We will also need an extension of the expander mixing lemma to counting paths
and cycles. The following can be proved using Lemma 2.1 or Proposition 2.2 and
induction, see [11].

######  Proposition 2.3 (Proposition 3.5 in [11]).

Let $G$ be an $(n,d,\lambda)$-graph, $k\geq 1$ an integer, and $U$ be a vertex
set with $\lambda\cdot\frac{n}{d}=o(|U|)$. Let $P_{k}(U)$ denote the number of
(labeled, possibly degenerate) paths with $k$ edges in $U$. Then we have

$P_{k}(U)=\left(1+o(1)\right)\frac{|U|^{k+1}d^{k}}{n^{k}}.$

######  Theorem 2.4 (Theorem 1.5 in [11]).

Let $G$ be an $(n,d,\lambda)$-graph and $U$ be a vertex set with
${\lambda\cdot\frac{n}{d}=o(|U|)}$. Let $C_{m}(U)$ denote the number of
(labeled, possibly degenerate) cycles of length $m$ with vertices in $U$. Then
we have

$\left|C_{m}(U)-\frac{|U|^{m}d^{m}}{n^{m}}\right|=O\left(\frac{\lambda|U|^{m-1}d^{m-1}}{n^{m-1}}+\frac{\lambda^{m-2}|U|^{2}d}{n}\right),$

The following is a straightforward technical lemma used in the arguments
below, showing that subsets of pseudo-random graphs cannot have too many
vertices of too large or small degree.

######  Lemma 2.5.

Let $G$ be an $(n,d,\lambda)$-graph. Assume $U\subset V(G)$ with
$\lambda(n/d)=o(|U|)$, then there exists a subset $U^{\prime}\subset U$ such
that $|U^{\prime}|=(1-o(1))|U|$ and

$\frac{|U|d}{2n}\leq\sum_{v\in U}\sum_{u\sim v}1\leq\frac{2|U|d}{n},$

for any $u\in U^{\prime}$.

###### Proof.

Let $L\subset U$ be the subset of vertices of $U$ with more than
$2\frac{|U|d}{n}$ neighbors in $U$ and $S$ the subset of vertices with fewer
than $\frac{1}{2}\frac{|U|d}{n}$ neighbors in $U$. Then by Lemma 2.1 we have
that

$|L|\cdot 2\frac{|U|d}{n}\leq
e(L,U)\leq|L||U|\frac{d}{n}+\lambda\sqrt{|L||U|},$

which implies that

$|L|\leq\frac{\lambda^{2}n^{2}}{d^{2}|U|}=o(|U|),$

by the assumption on the size of $U$. Similarly, $|S|=o(|U|)$ and taking
$U^{\prime}=U\setminus(S\cup L)$ gives the result.

∎

##  3 Counting configurations

In this section, we count several configurations which we will need in order
to prove Theorems 1.4 and 1.5. The most important configurations are pictured
in Figure 1.

Let $H_{1}$ be the number of $5$-tuples $(x,y,z,u,v)\in U^{5}$ such that

$x\sim y,y\sim z,z\sim u,u\sim v,u\sim x.$

Let $H_{2}$ be the number of $5$-tuples $(x,y,z,u,v)\in U^{5}$ such that

$x\sim u,u\sim z,z\sim y,x\sim y,u\sim v,v\sim y$

That is, $H_{2}$ is a copy of $K_{2,3}$. Let $H_{3}$ be the number of
$7$-tuples $(x,y,z,u,v,u^{\prime},x^{\prime})\in U^{7}$ such that

$x\sim y,y\sim z,z\sim u,u\sim x,u\sim v,$ $v\sim u^{\prime},u^{\prime}\sim
z,u^{\prime}\sim x^{\prime},x^{\prime}\sim y.$

We define two more configurations which are related to $H_{3}$. Let
$H_{3}^{+}$ be the same as configuration $H_{3}$ with the additional condition
that $x\sim u^{\prime}$. And let $H_{3}^{-}$ be the same configuration as
$H_{3}$ with the additional restriction that $x$ and $u^{\prime}$ are the same
vertex. That is, $H_{3}^{-}$ is $6$ vertices $x,y,z,u,v,x^{\prime}$ in $U$
satisfying

$x\sim y,~{}y\sim z,~{}z\sim u,~{}u\sim x,~{}x\sim
x^{\prime},~{}x^{\prime}\sim y,~{}x\sim v,~{}v\sim u,~{}x\sim z.$

Figure 1: Configurations $H_{1},H_{2},$ and $H_{3}$ Figure 2: Configurations
$H_{3}^{+},H_{3}^{-},$ and $H_{4}$

In this section, we show that for large enough subsets $U$, there will be a
subset $U^{\prime}\subset U$ with $|U^{\prime}|=(1-o(1))|U|$ such that we can
estimate the number of configurations in $U^{\prime}$ precisely. We do not
know if passing to the subset $U^{\prime}$ is necessary. However, we do this
so that we can bound the number of $K_{1,3}$ and $K_{1,4}$ in our subsets. We
will be interested in subsets $U$ which satisfy $\lambda\frac{n}{d}=o(|U|)$.
In some regimes, sets of this size do not have the expected number of stars on
$3$ and $4$ edges. For example, given an $(n,d,\lambda)$ graph with
$d=\sqrt{n}$, if a set $U$ has size $n^{3/4}$, then we expect $K_{1,4}(U)$ to
be $\Theta\left(n^{7/4}\right)$. On the other hand, taking a set of $n^{1/4}$
vertices and their neighborhoods gives a set $U$ with at least
$\Omega\left(n^{9/4}\right)$ copies of $K_{1,4}$. Note that if we wanted to
apply Theorem 1.6, we would require
$\lambda\left(\frac{n}{d}\right)^{4}=o(|U|)$ which is much larger than the
size of sets with which we wish to work. For our application to VC-dimension,
passing to a subset $U^{\prime}$ does not weaken the result, and so for the
trade-off of weakening the theorems in this section, we obtain in some cases
the best possible results for VC-dimension.

######  Theorem 3.1.

Let $G$ be an $(n,d,\lambda)$-graph and $U$ a subset of vertices with $\lambda
n/d=o(|U|)$. Then there is a subset $U^{\prime}\subset U$ with
$|U^{\prime}|=(1-o(1))|U|$ such that

$\left|H_{1}(U^{\prime})-\frac{|U^{\prime}|^{5}d^{5}}{n^{5}}\right|\ll\lambda^{2}\frac{|U^{\prime}|^{3}d^{2}}{n^{2}}+\lambda\frac{|U^{\prime}|^{4}d^{4}}{n^{4}}.$

###### Proof.

By Lemma 2.5, we may choose a subset $U^{\prime}\subset U$ with
$|U^{\prime}|=(1-o(1))|U|$ such that no vertex in $U^{\prime}$ has degree more
than $\frac{2|U|d}{n}$ in $U$.

Define $f(x,y)$ to be the number of paths of length $2$ of the form
$(x,y,u)\in(U^{\prime})^{3}$ with $x\sim y,y\sim u$. Define $g(z,w)=1_{z\sim
w},$ where the notation $1_{z\sim w}$ denotes the function that returns a 1 if
$z\sim w$ and $0$ otherwise.

Since $||f||_{1}$ is equal to the number of paths of length $2$ with vertices
in $U^{\prime}$, it follows from Proposition 2.3 that

$||f||_{1}=P_{2}(U^{\prime})=(1+o(1))\frac{|U^{\prime}|^{3}d^{2}}{n^{2}}$

and

$||g||_{1}=P_{1}(U^{\prime})=(1+o(1))\frac{|U^{\prime}|^{2}d}{n},$

under the condition that $\lambda\frac{n}{d}=o(|U^{\prime}|)$.

We now need to compute
$||f||_{2},||g||_{2},||F||_{2},||G||_{2},||F^{\prime}||_{2},||G^{\prime}||_{2}$
to apply Lemma 2.2. We will be slightly pedantic and write out more details
for the estimate of $||f||_{2},$ and let the reader fill in the very similar
details that we omit from the sequel.

$||f||_{2}^{2}=\hskip-5.0pt\sum_{x,y\in
U^{\prime}}\hskip-5.0ptf(x,y)f(x,y)=\hskip-5.0pt\sum_{x,y\in
U^{\prime}}|\\{(x,y,u)\in(U^{\prime})^{3}:x\sim y,y\sim u\\}|^{2}$
$=\hskip-5.0pt\sum_{x,y\in U^{\prime}}\hskip-5.0pt|\\{(x,y,u)\in V^{3}:x\sim
y,y\sim u\\}|\cdot|\\{(x,y,u^{\prime})\in V:x\sim y,y\sim u^{\prime}\\}|.$

So for an adjacent pair $x,y\in U^{\prime},$ the contribution to
$||f||_{2}^{2}$ is the number of pairs of vertices $u$ and $u^{\prime}$ in $V$
such that $y$ is adjacent to both. In the case that $u$ and $u^{\prime}$ are
distinct, we get a 3-star. In the (degenerate) case that $u=u^{\prime}$, we
get a path of length 2. Note that if $x$ and $y$ are not adjacent, they will
not contribute to the sum. So $||f||_{2}^{2}$ is the sum of the number of
3-stars in $G$ plus the number of 2-paths in $G.$ We now set out to estimate
these quantities.

We already saw that Proposition 2.3, that
$P_{2}(U^{\prime})=(1+o(1))|U^{\prime}|^{3}d^{2}n^{-2}.$ So it only remains to
estimate the number of 3-stars in $U^{\prime}$ and verify that this is much
more than $P_{2}(U^{\prime}).$ Using the fact that each vertex in $U^{\prime}$
has at most $2|U|d/n$ neighbors in $U$, we can conclude that the number of
3-stars is $O\left(|U|^{4}d^{3}n^{-3}\right)$, and this clearly dominates our
estimate of $P_{2}(U^{\prime}),$ as $\lambda n/d=o(U)$ by assumption, and
$\lambda\geq 1$ (by considering the trace of $A^{2}$ one can see that
$\lambda\gtrsim\sqrt{d}$). Putting everything together gives us the estimate

$||f||_{2}^{2}\ll\frac{|U|^{4}d^{3}}{n^{3}}.$

Moreover, by analogous arguments, neglecting similarly degenerate terms, one
has

$||g||_{2}^{2}=||g||_{1}^{2}=(1+o(1))\frac{|U^{\prime}|^{2}d}{n}.$

Similarly, $||F||_{2}^{2}$ is bounded by the number of paths of length $4$,
and $||F^{\prime}||_{2}^{2}$ is bounded by the number of stars with $4$ edges,
i.e.

$||F||_{2}^{2},||F^{\prime}||_{2}^{2}\ll\frac{|U|^{5}d^{4}}{n^{4}}.$

We now bound $||G^{\prime}||_{2}^{2}$ and $||G||_{2}^{2}$. It is clear that
these are at most the number of paths of length $2$, and so we have

$||G^{\prime}||_{2}^{2},||G||_{2}^{2}\ll|U|^{3}d^{2}/n^{2}.$

Putting these bounds to Proposition 2.2 and noting that

$\sum_{x\sim z,y\sim w}f(x,y)g(z,w)=H_{1}(U^{\prime})$

gives us

$\left|H_{1}(U^{\prime})-\frac{|U^{\prime}|^{5}d^{5}}{n^{5}}\right|\ll\lambda^{2}\frac{|U^{\prime}|^{3}d^{2}}{n^{2}}+\frac{d\lambda}{n}\frac{|U^{\prime}|^{4}d^{3}}{n^{3}}.$

This completes the proof. ∎

######  Theorem 3.2.

Let $G$ be an $(n,d,\lambda)$-graph and $U$ a subset of vertices such that
$\lambda n/d=o(|U|)$. Then there is a subset $U^{\prime}\subset U$ with
$|U^{\prime}|=(1-o(1))|U|$ such that

$\left|H_{2}(U^{\prime})-(1+o(1))\frac{|U^{\prime}|^{5}d^{6}}{n^{6}}\right|\ll\lambda^{2}\cdot\frac{|U^{\prime}|^{3}d^{2}}{n^{2}}.$

###### Proof.

By Lemma 2.5, we may choose a subset $U^{\prime}\subset U$ with
$|U^{\prime}|=(1-o(1))|U|$ such that no vertex in $U^{\prime}$ has degree more
than $\frac{2|U|d}{n}$ in $U$. As before, we will show that this subset
satisfies the conclusion.

We recall that $H_{2}(U^{\prime})$ counts the number of $5$-tuples
$(x,y,z,u,v)\in(U^{\prime})^{5}$ such that

$x\sim u,u\sim z,z\sim y,x\sim y,u\sim v,v\sim y.$

That is, it is the number of (labeled, possibly degenerate) $K_{2,3}$ in
$U^{\prime}$. For $u,y,z\in U^{\prime}$, define $f_{u}(y)$ as the number of
cycles of length $4$ with vertices in $U^{\prime}$ such that $u$ and $y$ form
a diagonal, define $g_{u}(z)=1$ if $u\sim z$ and $0$ otherwise. Summing over
all $u$ in $U^{\prime}$ and $y\sim z$, we have,

$H_{2}(U^{\prime})=\sum_{u\in U^{\prime}}\sum_{y\sim
z}f_{u}(y)g_{u}(z)=\sum_{u\in U^{\prime}}\langle f_{u},Ag_{u}\rangle.$

Applying Lemma 2.1 for each choice of $u$ and summing gives us

$\left|H_{2}(U^{\prime})-\frac{d}{n}\sum_{u}\sum_{y\in
U^{\prime}}f_{u}(y)\sum_{z\in U^{\prime}}g_{u}(z)\right|\ll\lambda\sum_{u\in
U^{\prime}}\left(\sum_{y}f_{u}(y)^{2}\right)^{1/2}\left(\sum_{z}g_{u}(z)^{2}\right)^{1/2}.$

Notice that

$\sum_{u,y,z\in U^{\prime}}f_{u}(y)g_{u}(z)=|H_{1}(U^{\prime})|.$

By the Cauchy-Schwarz inequality, one has

$\sum_{u\in
U^{\prime}}\left(\sum_{y}f_{u}(y)^{2}\right)^{1/2}\left(\sum_{z}g_{u}(z)^{2}\right)^{1/2}\leq\left(\sum_{u,y}f_{u}(y)^{2}\right)^{1/2}\cdot\left(\sum_{u,z}g_{u}(z)^{2}\right)^{1/2}.$

Now $\sum f_{u}(y)^{2}$ is the number of (labeled, possibly degenerate) copies
of $K_{2,4}$. This can be bounded above by the number of $K_{2,3}$ times the
degree of one of the vertices in the part of size $2$ (note that this is on
average giving up a factor of about $\frac{d}{n}$). Using the fact that each
vertex in $U^{\prime}$ has at most $2|U|d/n$ neighbors in $U$, we have

$\sum_{u}\sum_{y}f_{u}(y)^{2}\leq|H_{2}(U^{\prime})|\cdot\frac{2|U|d}{n}.$

Moreover, the sum $\sum_{u,z}g_{u}(z)^{2}$ equals $P_{1}(U^{\prime})$, so it
is $(1+o(1))|U^{\prime}|^{2}d/n$ by Lemma 2.1.

Putting these computations together and using Theorem 3.1, one has

$\left|H_{2}(U^{\prime})-(1+o(1))\frac{|U^{\prime}|^{5}d^{6}}{n^{6}}\right|\ll\lambda^{2}\cdot\frac{|U^{\prime}|^{3}d^{2}}{n^{2}}.$

This completes the proof.

∎

######  Remark 3.1.

The above two lemmas say that when $\lambda(n/d)^{3/2}=o(|U|)$, there is a
subset $U^{\prime}\subset U$ with $|U^{\prime}|\gg|U|$ such that

$H_{1}(U^{\prime})=(1+o(1))\frac{|U^{\prime}|^{5}d^{5}}{n^{5}},~{}H_{2}(U^{\prime})=o(H_{1}(U^{\prime})).$

In the proof of Theorem 3.2, if we assume that any two vertices in $U$ have at
most $\gamma$ common neighbors, and $\Lambda=\min\\{\gamma,2|U|d/n\\}$, then

$\sum_{u,y}f_{u}(y)^{2}\leq H_{2}(U^{\prime})\cdot\Lambda.$

This implies the following strengthened version.

######  Theorem 3.3.

Let $G$ be an $(n,d,\lambda)$-graph and $U$ a subset of vertices such that
$\lambda n/d=o(|U|)$. If any two vertices in $U$ have at most $\gamma$ common
neighbors, and $\Lambda=\min\\{\gamma,2|U|d/n\\}$, then there is a subset
$U^{\prime}\subset U$ with $|U^{\prime}|=(1-o(1))|U|$ such that

$\left|H_{2}(U^{\prime})-(1+o(1))\frac{|U^{\prime}|^{5}d^{6}}{n^{6}}\right|\ll\lambda^{2}\cdot\frac{|U^{\prime}|^{2}d}{n}\cdot\Lambda.$

Next we give estimates on $H_{3}^{+}$, the supergraph of $H_{3}$ with respect
to the number of copies of $H_{3}$, and finally we give an upper bound on
$H_{3}^{-}$. We were not able to give an asymptotic formula for $H_{3}$ and we
leave this as an interesting open problem. Later in the proof of Theorem 1.5
we will give only a lower bound on the number of $H_{3}$ and this will be
enough for our purposes. In order to estimate $H_{3}^{+}$ we will first need
to estimate one more configuration.

Define $H_{4}(U^{\prime})$ to be the number of $6$-tuples
$(y,z,u,v,u^{\prime},x)$ in $(U^{\prime})^{6}$ such that

$y\sim z,~{}z\sim u,~{}u\sim v,~{}v\sim u^{\prime},~{}u^{\prime}\sim
x,~{}x\sim y,~{}z\sim u^{\prime}.$

######  Theorem 3.4.

Let $G$ be an $(n,d,\lambda)$-graph and $U$ a subset of vertices such that
$|U|\gg\lambda(n/d)^{3/2}$. Then there is a subset $U^{\prime}\subset U$ with
$|U^{\prime}|=(1-o(1))|U|$ such that

$H_{4}(U^{\prime})\ll\frac{|U^{\prime}|^{6}d^{7}}{n^{7}}.$

###### Proof.

By Theorem 2.4, we have that the number of $C_{4}$ in $U$ is

$O\left(\frac{|U|^{4}d^{4}}{n^{4}}\right),$

since $|U|\gg\lambda(n/d)^{3/2}$.

Let $L$ be the set of vertices in $U$ which are contained in at least
$C|U|^{3}d^{4}/n^{4}$ copies of $C_{4}$ in $U$, and define
$U^{\prime}=U\setminus L$. Then for any $\epsilon>0$, there is a $C$ such that
$|U^{\prime}|\geq(1-\epsilon)|U|$ and every vertex in $U^{\prime}$ has at most
$C|U|^{3}d^{4}/n^{4}$ copies of $C_{4}$ containing it.

First we define

$f(z,u^{\prime})=\\#\\{(u,v)\in U^{\prime}\times U^{\prime}\colon z\sim
u,~{}u\sim v,~{}v\sim u^{\prime},~{}u^{\prime}\sim z\\},$

and $g(y,x)=1$ if $y\sim x$ and $0$ otherwise.

The strategy is to apply Proposition 2.2. It is clear that
$\sum_{z,u^{\prime}\in U^{\prime}}f(z,u^{\prime})$ counts the number of
$4$-cycles in $U^{\prime}$, so we have that

$\sum_{z,u^{\prime}\in
U^{\prime}}f(z,u^{\prime})=O\left(\frac{|U^{\prime}|^{4}d^{4}}{n^{4}}\right).$

Since $\lambda(n/d)=o(|U|)$, we have $\sum_{y,z\in
U^{\prime}}g(y,z)=(1+o(1))|U^{\prime}|^{2}d/n$ by Proposition 2.3.

On the other hand, $\sum_{z,u^{\prime}\in U^{\prime}}f(z,u^{\prime})^{2}$ is
at most $H_{4}(U^{\prime})$, and $\sum_{y,x\in
U^{\prime}}g(y,x)^{2}=\sum_{y,x\in U^{\prime}}g(y,x)\ll|U^{\prime}|^{2}d/n$.
In the setting of Proposition 2.2, we can check directly that
$\sum_{z}F(z)^{2}$ counts the number of pairs of $4$-cycles sharing a common
point, so is bounded by

$O\left(\frac{|U^{\prime}|^{7}d^{8}}{n^{8}}\right),$

by the definition of $U^{\prime}$. Moreover, $\sum_{y}G(y)^{2}$ is at most the
number of paths of length $2$ in $U^{\prime}$, which is at most
$O\left(|U^{\prime}|^{3}d^{2}/n^{2}\right)$ by Proposition 2.3. The same
estimates hold for $\sum_{u^{\prime}}F(u^{\prime})^{2}$ and
$\sum_{x}G(x)^{2}$. Putting these estimates together and noting that
$H_{4}(U^{\prime})=\sum_{x\sim u^{\prime},y\sim z}f(x,y)g(z,u^{\prime})$ gives
us by Proposition 2.2 that

$H_{4}(U^{\prime})\ll\frac{|U^{\prime}|^{6}d^{7}}{n^{7}}+\lambda^{2}H_{4}(U^{\prime})^{1/2}\left(\frac{|U^{\prime}|^{2}d}{n}\right)^{1/2}+\lambda\frac{|U^{\prime}|^{5}d^{6}}{n^{6}}.$

Thus,

$H_{4}(U^{\prime})\ll\frac{|U^{\prime}|^{6}d^{7}}{n^{7}}+\lambda^{4}\frac{|U^{\prime}|^{2}d}{n}\ll\frac{|U^{\prime}|^{6}d^{7}}{n^{7}}.$

∎

With this in hand, we are able to estimate $H_{3}^{+}$

######  Theorem 3.5.

Let $G$ be an $(n,d,\lambda)$-graph and $U$ a subset of vertices such that
$|U|\gg\lambda(n/d)^{3/2}$. Then there is a subset $U^{\prime}\subset U$ with
$|U^{\prime}|=(1-o(1))|U|$ such that

$\left|H_{3}^{+}(U^{\prime})-\frac{H_{3}(U^{\prime})d}{n}\right|\ll\lambda\left(H_{2}(U^{\prime})\frac{|U^{\prime}|d}{n}\right)^{1/2}\left(\frac{|U^{\prime}|^{6}d^{8}}{n^{8}}+\lambda
H_{2}(U^{\prime})\right)^{1/2}.$

###### Proof.

As before, by Lemma 2.5, we pass to a subset $U^{\prime}\subset U$ with
$|U^{\prime}|=(1-o(1))|U|$ such that no vertex in $U^{\prime}$ has degree more
than $\frac{2|U|d}{n}$ in $U$. We furthermore may assume that the conclusion
of Theorem 3.4 holds on $U^{\prime}$.

We recall that $H_{3}^{+}(U^{\prime})$ counts the number of $7$-tuples
$(x,y,z,u,v,u^{\prime},x^{\prime})\in(U^{\prime})^{7}$ such that

$x\sim y,y\sim z,z\sim u,u\sim x,u\sim v,v\sim u^{\prime},u^{\prime}\sim
z,u^{\prime}\sim x^{\prime},x^{\prime}\sim y,x\sim u^{\prime}.$

To prove this theorem, we proceed as follows.

Given $y,z,v\in U^{\prime}$ such that $y\sim z$, we define

$f_{y,z,v}(u^{\prime}):=\\#\\{x^{\prime}\in U^{\prime}\colon x^{\prime}\sim
y,u^{\prime}\sim z,u^{\prime}\sim v,u^{\prime}\sim x^{\prime}\\},$

and

$g_{y,z,v}(x):=\\#\\{u\in U^{\prime}\colon x\sim y,x\sim u,u\sim v,u\sim
z\\}.$

Note that $f_{y,z,v}(u^{\prime})$ is the number of vertices in
$N(u^{\prime})\cap N(y)$ times the indicator that $u^{\prime}\in N(z)\cap
N(v)$ and $g_{y,z,v}(x)$ is the number of vertices in $N(v)\cap N(x)\cap N(z)$
times the indicator that $x\in N(y)$.

Then we have that

$\displaystyle H_{3}^{+}(U^{\prime})$ $\displaystyle=\sum_{y,z,v,y\sim
z}\sum_{x\sim u^{\prime}}f_{y,z,v}(u^{\prime})g_{y,z,v}(x)=\sum_{y,z,v,y\sim
z}\langle f,Ag\rangle.$

We first observe that

$\sum_{y,z,v,y\sim z}||f_{y,z,v}||_{1}||g_{y,z,v}||_{1}=H_{3}(U^{\prime}).$

Next, let $y\sim z$ and $v$ be fixed. For each $u^{\prime}$, we have that
$(f_{y,z,v}(u^{\prime}))^{2}$ is at most the number of homomorphisms to
$K_{2,3}$ where $y$ and $u^{\prime}$ are in the part of size $2$ and $z$ is in
the part of size $3$, times the indicator that $u^{\prime}\sim v$. Therefore,
this is at most the number of $K_{2,3}$ with $y,u^{\prime}$ in the part of
size $2$ times the degree of $u^{\prime}$. This implies

$\sum_{y,z,v,y\sim z}||f_{y,z,v}||_{2}^{2}\ll
H_{2}(U^{\prime})\cdot\frac{|U|d}{n}.$

In the next step, we bound the sum $\sum_{y,z,v,y\sim z}||g_{y,z,v}||_{2}^{2}$
which is much more complicated. We denote this sum by $M$. We have $M$ counts
the number of $6$-tuples $(y,z,u,v,u^{\prime},x)\in U^{\prime}$ such that

$y\sim z,~{}z\sim u,~{}u\sim v,~{}v\sim u^{\prime},~{}u^{\prime}\sim
x,~{}x\sim y,~{}x\sim u,~{}z\sim u^{\prime}.$

To bound $M$ from above, we proceed as follows. More precisely, given $z\sim
u^{\prime}$, define

$k_{z,u^{\prime}}(u)=\\#\\{v\in U^{\prime}\colon v\sim u,v\sim
u^{\prime},z\sim u\\},$

and

$h_{z,u^{\prime}}(x)=\\#\\{y\in U^{\prime}\colon y\sim x,y\sim z,x\sim
u^{\prime}\\}.$

Then it is clear that

$M=\sum_{\begin{subarray}{c}x,u\in U^{\prime}\\\ x\sim
u\end{subarray}}\sum_{\begin{subarray}{c}z,u^{\prime}\in U^{\prime}\\\ z\sim
u^{\prime}\end{subarray}}k_{z,u^{\prime}}(u)h_{z,u^{\prime}}(x).$

To apply Lemma 2.1, the following estimates are needed.

$\sum_{\begin{subarray}{c}z,u^{\prime}\in U^{\prime}\\\ ~{}z\sim
u^{\prime}\end{subarray}}|k_{z,u^{\prime}}(u)|^{2}=H_{2}(U^{\prime}),~{}\sum_{\begin{subarray}{c}z,u^{\prime}\in
U^{\prime}\\\ ~{}z\sim
u^{\prime}\end{subarray}}|h_{z,u^{\prime}}(x)|^{2}=H_{2}(U^{\prime}).$

We also need to bound
$\sum_{z,u^{\prime}}k_{z,u^{\prime}}(u)h_{z,u^{\prime}}(x)$. This sum counts
the number of $6$-tuples $(y,z,u,v,u^{\prime},x)\in U^{\prime}$ such that

$y\sim z,~{}z\sim u,~{}u\sim v,~{}v\sim u^{\prime},~{}u^{\prime}\sim
x,~{}x\sim y,~{}z\sim u^{\prime}.$

Note that this is exactly $H_{4}(U^{\prime})$. By Theorem 3.4, we have that

$H_{4}(U^{\prime})\ll\frac{|U^{\prime}|^{6}d^{7}}{n^{7}},$

since $|U^{\prime}|\gg\lambda(n/d)^{3/2}$. Applying Lemma 2.1, we have

$M=\sum_{z\sim u^{\prime}}\langle
k_{z,u^{\prime}},Ah_{z,u^{\prime}}\rangle\ll\frac{|U^{\prime}|^{6}d^{8}}{n^{8}}+\lambda
H_{2}(U^{\prime}).$

Hence, the theorem follows from Lemma 2.1. ∎

######  Theorem 3.6.

Let $G$ be an $(n,d,\lambda)$-graph and $U$ a subset of vertices such that
$n\lambda/d=o(|U|)$, then there is a subset $U^{\prime}\subset U$ of size
$(1-o(1))|U|$ such that

$H_{3}^{-}(U^{\prime})\ll\frac{|U^{\prime}|^{6}d^{7}}{n^{7}}+\lambda^{2}\frac{|U^{\prime}|^{4}d^{4}}{n^{4}}+\lambda\frac{|U^{\prime}|^{5}d^{5}}{n^{5}}+\lambda^{2}\frac{|U^{\prime}|^{4}d^{7/2}}{n^{7/2}}+\lambda^{3}\frac{|U^{\prime}|^{3}d^{5/2}}{n^{5/2}}+\lambda^{4}\frac{|U^{\prime}|^{2}d}{n}.$

###### Proof.

As before, pass to a subset $U^{\prime}$ of size $(1-o(1))|U^{\prime}|$ where
each vertex in $U^{\prime}$ has at most $\frac{2|U|d}{n}$ neighbors in $U$.

Fix $z\in U^{\prime}$. Define $f_{z}(x)$ to be the number of tuples
$(z,x,v,u)\in U^{\prime 4}$ such that $z\sim x,x\sim v,v\sim u,u\sim z$, and
$g_{z}(x^{\prime})$ to be the number of tuples $(z,x^{\prime},y)\in U^{\prime
3}$ such that $z\sim y,y\sim x^{\prime}$.

Then it is clear that

$H_{3}^{-}(U^{\prime})\leq\sum_{z\in U}\sum_{x\sim
x^{\prime}}f_{z}(x)g_{z}(x^{\prime}).$

We first note that the sum $\sum_{z}||f_{z}||_{1}||g_{z}||_{1}$ is equal to
the number of tuples $(z,x,v,u,y,x^{\prime})$ such that

$z\sim x,~{}x\sim v,~{}v\sim u,~{}u\sim z,~{}z\sim y,~{}y\sim x^{\prime}.$

This number is at most $H_{1}(U^{\prime})\cdot 2|U|d/n$. To bound
$H_{3}^{-}(U^{\prime})$ from above, we will apply Lemma 2.1. To proceed
further, we need to bound the $L^{2}$-norm of $f_{z}$ and $g_{z}$. In the way
we define the function $f_{z}$ and $g_{z}$, it is not hard to see that the sum
$\sum_{z}||f_{z}||_{2}^{2}$ is at most the number of $6$-cycles
$C_{6}(U^{\prime})$, which by Theorem 2.4 is bounded from above by

$(1+o(1))\frac{|U^{\prime}|^{6}d^{6}}{n^{6}}+O\left(\frac{\lambda^{4}|U^{\prime}|^{2}d}{n}\right).$

Similarly, we also have the sum $\sum_{z}||g_{z}||_{2}^{2}$ is at most the
number of $4$-cycles $C_{4}(U^{\prime})$, which is bounded from above by

$(1+o(1))\frac{|U^{\prime}|^{4}d^{4}}{n^{4}}+O\left(\frac{\lambda^{2}|U^{\prime}|^{2}d}{n}\right).$

In other words, we can conclude that

$H_{3}^{-}(U^{\prime})\leq\frac{H_{1}(U^{\prime})|U^{\prime}|d^{2}}{n^{2}}+\lambda\frac{|U^{\prime}|^{5}d^{5}}{n^{5}}+\lambda^{2}\frac{|U^{\prime}|^{4}d^{7/2}}{n^{7/2}}+\lambda^{3}\frac{|U^{\prime}|^{3}d^{5/2}}{n^{5/2}}+\lambda^{4}\frac{|U^{\prime}|^{2}d}{n}.$

Applying Theorem 3.1 completes the proof. ∎

######  Remark 3.2.

In practice, configurations in Theorems 3.5 and 3.6 might not exist.

##  4 Proof of Theorem 1.4

To prove Theorem 1.4, we need to show that there exists a set of two distinct
points, say $x_{1},x_{2}\in U$, such that the restriction of $\mathcal{H}$ to
$U$ yields every possible function from $\\{x_{1},x_{2}\\}$ to $\\{0,1\\}$.
This is equivalent to saying that there exists $u^{*},u_{1},u_{2},u_{12}\in U$
such that

$x_{1}\sim u_{12},x_{2}\sim u_{12},$ $x_{1}\sim u_{1},x_{2}\not\sim u_{1},$
$x_{1}\not\sim u_{2},x_{2}\sim u_{2},$

and

$x_{1}\not\sim u^{*},x_{2}\not\sim u^{*}.$

We first prove the existence of $u_{1},u_{2},u_{12}$ which are joined to
$x_{1}$ and $x_{2}$ in the prescribed way. By Lemma 2.5 and Theorem 3.1, we
may choose a subset $U^{\prime}\subset U$ with $|U^{\prime}|=(1-o(1))|U|$ such
that no vertex in $U^{\prime}$ has degree more than $\frac{2|U|d}{n}$ in $U$
and that satisfies

$\left|H_{1}(U^{\prime})-\frac{|U^{\prime}|^{5}d^{5}}{n^{5}}\right|\ll\lambda^{2}\frac{|U^{\prime}|^{3}d^{2}}{n^{2}}+\lambda\frac{|U^{\prime}|^{4}d^{4}}{n^{4}}.$

We will show that $x_{1},x_{2},u_{1},u_{2},u_{12}$ may be found in
$U^{\prime}$. Afterwards, we will show that by the definition of $U^{\prime}$
there will be a vertex $u^{*}\in U$ which is adjacent to neither $x_{1}$ nor
$x_{2}$. Hence it suffices to show the existence of these $5$ vertices in
$U^{\prime}$ with the prescribed edges and non-edges.

We do this by finding a path on $5$ vertices $u_{1}\sim x_{1}\sim u_{12}\sim
x_{2}\sim u_{2}$. Such a path will satisfy our requirements if and only if we
have $u_{1}\not\sim x_{2}$ and $u_{2}\not\sim x_{1}$. In order to guarantee
the existence of such a path we count all paths and then count paths where at
least one of the forbidden edges is present.

We know from Proposition 2.3 that the number of paths on $5$ vertices in
$U^{\prime}$ with it at least

$(1-o(1))\frac{|U^{\prime}|^{5}d^{4}}{n^{4}},$ (1)

because of the restriction that $\frac{\lambda n}{d}=o(|U|)$. Note that there
are also this many paths where all $5$ vertices are distinct, again by
Proposition 2.3. Such a path will satisfy our requirements unless $x_{1}\sim
u_{2}$ or $x_{2}\sim u_{1}$. If either of these forbidden edges occurs, we
have found configuration $H_{1}$.

By the definition of $U^{\prime}$ we have that

$H_{1}(U^{\prime})\leq\frac{|U^{\prime}|^{5}d^{5}}{n^{5}}+O\left(\lambda^{2}\frac{|U^{\prime}|^{3}d^{2}}{n^{2}}+\frac{\lambda|U^{\prime}|^{4}d^{4}}{n^{4}}\right),$

This quantity is much smaller than the number of paths in (1) by the
hypothesis on the size of $U$. Choosing any vertex $u^{*}\in U$ which is not
in $N(x_{1})\cup N(x_{2})$ completes the proof. We are guaranteed that such a
vertex exists, as $x_{1},x_{2}\in U^{\prime},$ so neither has more than
$\frac{2|U|d}{n}$ neighbors in $U^{\prime}$. So $|N(x_{1})\cup
N(x_{2})|\leq\frac{4|U|d}{n},$ leaving at least $|U^{\prime}|-\frac{4|U|d}{n}$
choices for $u^{*}$ in $U^{\prime}\setminus(N(x_{1})\cup N(x_{2})).$ The
number of choices of $u^{*}$ is then strictly positive by our assumptions.

##  5 Proof of Theorem 1.5

The proof of Theorem 1.5 is a bit involved, so we first give a sketch.

###  5.1 Sketch of proof

To prove the VC-dimension is at least $3$, we need to find vertices
$x_{1},x_{2},x_{3},y_{1},y_{2},y_{3},y_{12},y_{13},y_{23},y_{13},y^{*}\in U$
with $x_{1},x_{2},x_{3}$ distinct such that

  1. 1.

$x_{1}\sim y_{123}$, $x_{2}\sim y_{123}$, $x_{3}\sim y_{123}$

  2. 2.

$x_{1}\sim y_{12}$, $x_{2}\sim y_{12}$, $x_{3}\not\sim y_{12}$, and similarly
for $y_{13}$ and $y_{23}$.

  3. 3.

$x_{1}\sim y_{1}$, $x_{2}\not\sim y_{1}$, $x_{3}\not\sim y_{1}$, and similarly
for $y_{2}$ and $y_{3}$.

  4. 4.

$x_{1}\not\sim y^{*}$, $x_{2}\not\sim y^{*}$, $x_{3}\not\sim y^{*}$.

If we can find vertices in such a configuration, then the set
$\\{h_{x_{1}},h_{x_{2}},h_{x_{3}}\\}$ is shattered by $\mathcal{H}(U)$ and
this shows that the VC-dimension of $U$ is at least $3$. We again note that
for the definition of shattering, it does not matter what adjacency or non-
adjacency we see between $x_{i}$ and $x_{j}$ or between any of the $y$
vertices. We also note that for the definition of shattering to be satisfied,
it is possible that some $y$ and some $x_{j}$ are the same vertex. However, we
will avoid this situation because the possible presence of loops in our graphs
make it hard to analyze. To prove that we can find a set of vertices with the
above properties, we use the count of configurations in Section 3.

To prove Theorem 1.5, we do the following steps.

Step 1: We first pass to a subset $U^{\prime}$ where we may count the
configurations from Section 3. Then we argue that it is enough to find
vertices $x_{1},x_{2},x_{3},y_{123},y_{12},y_{23},y_{13}$ in $U^{\prime}$.

Step 2: Next we count the number of configurations $H_{1}$ and use Cauchy-
Schwarz to lower bound the number of tuples satisfying

  * •

$x_{1}\sim y_{123},x_{2}\sim y_{123},x_{3}\sim y_{123}$

  * •

$x_{1}\sim y_{12},x_{2}\sim y_{12}$

  * •

$x_{1}\sim y_{13},x_{3}\sim y_{13}$

  * •

$x_{2}\sim y_{23},x_{3}\sim y_{23}$

  * •

$x_{2}\not\sim y_{13}$

  * •

$x_{1}\neq x_{2}$, $x_{3}\neq x_{2}$

  * •

$y_{123}\neq y_{12}$, $y_{123}\neq y_{23}$

Step 3:

In the previous step, some of the vertices may overlap. Since we must have
that $x_{1}\not=x_{3}$, next we show that the number of configurations in Step
$2$ with $x_{1}=x_{3}$ is much smaller than the total.

Step 4:

After the step $3$, we get a lower bound on the number of tuples satisfying

  * •

$x_{1}\sim y_{123},x_{2}\sim y_{123},x_{3}\sim y_{123}$

  * •

$x_{1}\sim y_{12},x_{2}\sim y_{12}$

  * •

$x_{1}\sim y_{13},x_{3}\sim y_{13}$

  * •

$x_{2}\sim y_{23},x_{3}\sim y_{23}$

  * •

$x_{2}\not\sim y_{13}$

  * •

$x_{1}\neq x_{2}$, $x_{3}\neq x_{2}$, $x_{1}\neq x_{3}$

  * •

$y_{123}\neq y_{12}$, $y_{123}\neq y_{23}$

Step 5: For those tuples in the Step $4$, we need to remove tuples with
$y_{12}\sim x_{3}$ and $y_{23}\sim x_{1}$ and tuples with $x_{2}=y_{12}$ or
$x_{3}=y_{12}$. If there is an adjacency we have the configuration
$H_{3}^{xu^{\prime}}$ and if there is an overlap of vertices we have the
configuration $H_{3}^{-}$.

Step 6:

Using the assumption in the statement of the theorem, we conclude the proof.

###  5.2 Details

###### Proof of Theorem 1.5.

First we pass to a subset $U^{\prime}$ where our configurations are well-
behaved. By Lemma 2.5, we may consider a subset $U^{\prime}\subset U$ such
that all vertices in $U^{\prime}$ have between $\frac{1}{2}\frac{|U|d}{n}$ and
$2\frac{|U|d}{n}$ neighbors in $U$. By Remark 3.1 and Theorem 3.5, we may
assume that $H_{1}(U^{\prime})$ is close to its expected value, that
$H_{2}(U^{\prime})=o(H_{1}(U^{\prime}))$, and that
$H_{3}^{+}(U^{\prime})\leq\epsilon(|U|^{7}d^{9}/n^{9}+H_{3}(U^{\prime}))$
where $\epsilon$ can be taken arbitrarily small by choosing $C$ large enough
in the hypotheses of the theorem.

We focus on the existence of the vertices
$x_{1},x_{2},x_{3},y_{123},y_{12},y_{23},y_{13}$ in $U^{\prime}$. If we can
find such a subconfiguration, then by the assumption in the hypotheses of the
theorem, we may find vertices $y_{1},y_{2},y_{3}$. Since $|U|$ is much larger
than $\frac{|U|d}{n}$ and the vertices in $U^{\prime}$ have at most
$2\frac{|U|d}{n}$ neighbors in $U$, we may also find the vertex $y^{*}$ which
completes the configuration, as in the final step of the proof of Theorem 1.4.
Therefore it suffices to find the vertices
$x_{1},x_{2},x_{3},y_{123},y_{12},y_{23},y_{13}$ in $U^{\prime}$ satisfying
the adjacency and non-adjacency conditions. Note that this is exactly
configuration $H_{3}$.

Since each vertex in $U^{\prime}$ has at most $2|U|d/n$ neighbors, the number
of $3$-stars is at most $8|U|^{4}d^{3}/n^{3}$. Under the condition $\lambda
n/d=o(|U|)$, we also know from Proposition 2.3 that the number of $3$-paths is
$(1+o(1))|U|^{4}d^{3}/n^{3}$ and from Theorem 2.4 that
$C_{4}(U)=(1+o(1))\frac{|U|^{4}d^{4}}{n^{4}}$. For any $\\{x,y,z,u,v\\}$ with
$x\sim y,y\sim z,z\sim u,u\sim x,u\sim v$ (that is, that form configuration
$H_{1}$), if $x=z$ we have a $P_{3}$, if $y=u$ we have a star on $3$ edges, if
$v\in\\{x,y,z\\}$ we have a $4$-cycle, and if $y\sim v$ we have configuration
$H_{2}$.

So, it follows from Remark 3.1 that the number of tuples in $U^{\prime}$
satisfying

$x\sim y,y\sim z,z\sim u,u\sim x,u\sim v,y\not\sim v,x\neq z,y\neq
u,v\not\in\\{x,y,z\\}$ (2)

is at least $(1-\epsilon)|H_{1}|$ as long as $|U^{\prime}|\geq
C\lambda(n/d)^{3/2}$, for any $\epsilon$ and a large enough constant $C$.

We denote the set of those tuples by $H_{1}^{\prime}$. We will define the
notation $H_{1}^{\prime}(x,y,z,u,v)$ as the indicator that $x,y,z,u,v$ satisfy
(2), that is that they form a configuration in $H_{1}^{\prime}$. Define

$f(y,z,v)=\sum_{x,u\in U^{\prime}}H_{1}^{\prime}(x,y,z,u,v).$

Then we have that

$\sum_{y,z,v,~{}y\sim z}(f(y,z,v))^{2}=H_{3}(U^{\prime}).$

We will complete the proof by bounding this number from below and then showing
that the number of these homomorphisms which are either not injective or which
have an edge that is forbidden is smaller than the total number. Proceeding
with this, we have

$\frac{|U|^{10}d^{10}}{n^{10}}\ll|H_{1}^{\prime}|^{2}=\left(\sum_{y,z,v\in
U,~{}y\sim
z}f(y,z,v)\right)^{2}\leq\sum_{y,z,v}f(y,z,v)^{2}\cdot\sum_{y,z,v}1_{y\sim
z}.$

Notice that

$\sum_{y,z,v}1_{y\sim
z}\ll|U^{\prime}|\cdot\frac{|U^{\prime}|d}{n}\cdot|U^{\prime}|,$

by the degree restriction on $U^{\prime}$. This means that

$\sum_{y,z,v}f(y,z,v)^{2}\gg\frac{|U^{\prime}|^{7}d^{9}}{n^{9}}.$

Given a fixed $y\sim z$ and $v$, the quantity $(f(y,z,v))^{2}$ counts the
number of $4$-tuples $(x,u,x^{\prime},u^{\prime})$ so that
$H_{1}^{\prime}(x,y,z,u,v)=H_{1}^{\prime}(x^{\prime},y,z,u^{\prime},v)=1$. In
Figure 1, we think of $y,z,v$ as playing the roles of $x_{1},y_{123},y_{23}$
respectively, and we hope for a $4$-tuple $(x,u,x^{\prime},u^{\prime})$ that
play the roles of $(y_{13},x_{3},y_{12},x_{2})$. By the definition of
$H_{1}^{\prime}$, we have that each $\\{x,y,z,u,v\\}$ forming a copy of
$H_{1}^{\prime}$ satisfies $x\not=z$, $y\not=u$, $v\not\in\\{x,y,z\\}$, and
$y\not\sim v$.

This means that the number of tuples
$(x_{1},x_{2},x_{3},y_{12},y_{13},y_{23},y_{123})\in(U^{\prime})^{7}$ such
that

  * •

$x_{1}\sim y_{123},x_{2}\sim y_{123},x_{3}\sim y_{123}$

  * •

$x_{1}\sim y_{12},x_{2}\sim y_{12}$

  * •

$x_{1}\sim y_{13},x_{3}\sim y_{13}$

  * •

$x_{2}\sim y_{23},x_{3}\sim y_{23}$

  * •

$x_{1}\neq x_{2}$, $x_{1}\neq x_{3}$

  * •

$y_{123}\neq y_{12}$, $y_{123}\neq y_{13}$, $y_{123}\neq y_{23}$.

  * •

$y_{23}\not\in\\{y_{13},y_{12},x_{1},x_{2}\\}$

  * •

$x_{1}\not\sim y_{23}$

is at least $\Omega\left(|U|^{7}d^{9}/n^{9}\right)$. Such a $7$-tuple
satisfies all of our conditions unless one of the following occurs.

  * •

$y_{12}=y_{13}$

  * •

$x_{2}=x_{3}$

  * •

$x_{2}=y_{13}$

  * •

$x_{3}=y_{12}$

  * •

$x_{2}\sim y_{13}$

  * •

$x_{3}\sim y_{12}$

If $x_{2}\sim y_{13}$ or $x_{3}\sim y_{12}$, we get a configuration isomorphic
to $H_{3}^{+}$. Hence by Theorem 3.5, the number of these is at most
$\epsilon(|H_{3}(U^{\prime})|)$ whenever

$|U^{\prime}|\geq C\lambda(n/d)^{13/7},$ (3)

for any $\epsilon$ and a large enough $C$. If $x_{2}=x_{3}$, then the vertices
$\\{x_{1},x_{2},y_{12},y_{13},y_{123}\\}$ form configuration $H_{2}$ and
furthermore $y_{23}\sim x_{2}$. Thus the number of $6$-tuples of this form is
bounded above by $|H_{2}(U^{\prime})|\cdot\frac{2|U|d}{n}$. By Theorem 3.2,
this is at most

$O\left(\frac{|U|^{6}d^{7}}{n^{7}}+\lambda^{2}\frac{|U|^{4}d^{3}}{n^{3}}\right).$

This is smaller than $\epsilon|U^{\prime}|^{7}d^{9}/n^{9}$ when

$|U|\geq C\lambda^{2/3}(n/d)^{2},$ (4)

for a large enough absolute constant $C$. Similarly, if $y_{12}=y_{13}$, then
the vertices $\\{y_{12},y_{123},x_{1},x_{2},x_{3}\\}$ form a $H_{2}$ and
additional $y_{23}$ is adjacent to $x_{2}$ (and $x_{3})$. Hence the number of
$6$-tuples of this form is also bounded above by

$O\left(\frac{|U|^{6}d^{7}}{n^{7}}+\lambda^{2}\frac{|U|^{4}d^{3}}{n^{3}}\right).$

Finally, if $x_{2}=y_{13}$ or equivalently if $x_{3}=y_{12}$, then we have
configuration $H_{3}^{-}$. By Theorem 3.6, the number of these is at most

$O\left(\frac{|U^{\prime}|^{6}d^{7}}{n^{7}}+\lambda^{2}\frac{|U^{\prime}|^{4}d^{4}}{n^{4}}+\lambda\frac{|U^{\prime}|^{5}d^{5}}{n^{5}}+\lambda^{2}\frac{|U^{\prime}|^{4}d^{7/2}}{n^{7/2}}+\lambda^{3}\frac{|U^{\prime}|^{3}d^{5/2}}{n^{5/2}}+\lambda^{4}\frac{|U^{\prime}|^{2}d}{n}\right),$

which is smaller than $|U^{\prime}|^{7}d^{9}/n^{9}$ when

$|U|\geq
C\max\\{\lambda^{2/3}(n/d)^{2},\lambda(n/d)^{3/2},~{}\lambda^{3/4}(n/d)^{13/8},~{}\lambda^{4/5}(n/d)^{8/5}\\}\geq
C\max\left\\{\lambda^{2/3}(n/d)^{2},\lambda(n/d)^{13/7}\right\\}.$ (5)

Therefore if $C$ is chosen to be a large enough absolute constant, we have
that there is a $7$-tuple such that none of the forbidden adjacencies or
vertex identifications occur, and therefore the VC-dimension of
$\mathcal{H}(U)$ is at least $3$ under

$|U|\geq C\max\left\\{\lambda^{2/3}(n/d)^{2},\lambda(n/d)^{13/7}\right\\}.$

∎

##  6 Proofs of Theorems 1.7, 1.8, and 1.9

The proofs of Theorems 1.7 and 1.9 are almost the same, so we only present one
of them.

###### Proof of Theorem 1.7.

The only detail we need to check is the first condition, namely, given any
three vertices $v_{1},v_{2},v_{3}$ in $U$, we can find three vertices
$u_{1},u_{2},u_{3}$ in $U$ such that $u_{i}\cdot v_{j}=1$ if and only if
$i=j$.

Using the fact that any two distinct hyperplanes in $\mathbb{F}_{q}^{t}$
intersect in at most $q^{t-2}$ points. This means that $|N(v_{i})\cap
N(v_{j})|\leq q^{t-2}$. On the other hand, by Lemma 2.5 we may pass to a
subset $U^{\prime}$ such that for each $i$, $|N(v_{i})\cap
U^{\prime}|=\Theta(q^{-1}|U|)$. So, the condition $|U|\geq Cq^{t-1}$ is enough
to guarantee that we will find such vertices $v_{1},v_{2},v_{3}$ as long as
$C$ is chosen large enough. ∎

###### Proof of Theorem 1.8.

In this particular setting, we can use the geometric properties to improve the
argument in the proof of Theorem 1.5. We will run the same proof as in Theorem
1.5 except we also remove all unit vectors from $U$ when defining
$U^{\prime}$. Since there are at most $O(q^{2})$ unit vectors in
$\mathbb{F}_{q}^{3}$, we still have that $|U^{\prime}|=(1+o(1))|U|$. Now we
use geometric properties to show that for some of the configurations, we
either have better upper bounds or they do not exist.

More precisely, when estimating copies of configuration 2, the fact that the
intersection of two distinct planes is either a line or a null set, we have
that any two vertices in the graph have at most $q$ common neighbors. We may
therefore use Theorem 3.3 and this implies that the condition (4) is replaced
by

$|U^{\prime}|\geq Cq^{5/2}.$

Next we show that any copy of $H_{3}^{-}$ contains a unit vector and hence by
the definition of $U^{\prime}$ we may ignore the configuration. Assume there
is a copy of $H_{3}^{-}$ with labels as in Figure 1, so $x=u^{\prime}$. By the
adjacencies, we have that the planes $\\{w:v\cdot w=1\\}$, $\\{w:x\cdot
w=1\\}$, and $\\{w:z\cdot w=1\\}$ all contain $u$. Since the intersection of
three planes is either a line or is empty, the intersection must be a line.
But the line containing $u$ and $x$ is the intersection of the planes
$\\{w:v\cdot w=1\\}$ and $\\{w:z\cdot w=1\\}$, and hence the line containing
$x$ and $u$ is also the intersection of all three planes. But this now implies
that $x\cdot x=1$. Hence, the condition (5) is not needed.

With a similar argument and the fact that $x_{1}\not\sim y_{23}$, we can check
that the configuration $H_{3}^{+}$ does not appear (this argument appears at
the end of the paper [6]). So the condition (3) is not needed.

In conclusion, in this setting, we only need the condition $|U^{\prime}|\geq
Cq^{5/2}$ to ensure that the dimension is at least three.

To see the upper bound on the VC-dimension in $\mathbb{F}_{q}^{3}$, notice
that no quadruple of points can be shattered, as any three of them determine a
plane. Since dot-products are constant on planes, any quadruple of points that
have the same non-zero dot product with a point will lie on a plane. Thus any
triple of them will lie on the same plane. So if any three of the points from
the quadruple determine a given non-zero dot product with a point in
$\mathbb{F}_{q}^{3},$ so will the fourth, and we cannot shatter any set of
four points.

This completes the proof. ∎

##  7 Acknowledgements

T. Pham would like to thank to the VIASM for the hospitality and for the
excellent working conditions. M. Tait was partially supported by National
Science Foundation grant DMS-2011553.

## References

  * [1] Martin Anthony, Graham Brightwell, and Colin Cooper, _The Vapnik-Chervonenkis dimension of a random graph_ , Discrete Mathematics 138 (1995), no. 1-3, 43–56.
  * [2] Ruben Ascoli, Livia Betti, Justin Cheigh, Alex Iosevich, Ryan Jeong, Xuyan Liu, Brian McDonald, Wyatt Milgrim, Steven J Miller, Francisco Romero Acosta, et al., _VC-dimension and distance chains in $\mathbb{F}_{q}^{d}$_, arXiv preprint arXiv:2210.03058 (2022).
  * [3] Eiichi Bannai, Osamu Shimabukuro, and Hajime Tanaka, _Finite analogues of non-Euclidean spaces and Ramanujan graphs_ , European Journal of Combinatorics 25 (2004), no. 2, 243–259.
  * [4] D Fitzpatrick, A Iosevich, B McDonald, and E Wyman, _The VC-dimension and point configurations in $\mathbb{F}_{q}^{2}$_, arXiv preprint arXiv:2108.13231 (2021).
  * [5] Wilhelmus Hubertus Haemers, _Eigenvalue techniques in design and graph theory_ , (1980).
  * [6] A Iosevich, B McDonald, and M Sun, _Dot products in $\mathbb{F}_{q}^{3}$ and the Vapnik-Chervonenkis dimension_, Discrete Mathematics 346 (2023), no. 1, 113096.
  * [7] Michael Krivelevich and Benny Sudakov, _Pseudo-random graphs_ , More sets, graphs and numbers, Springer, 2006, pp. 199–262.
  * [8] Wing Man Kwok, _Character tables of association schemes of affine type_ , European journal of combinatorics 13 (1992), no. 3, 167–185.
  * [9] Jiri Matousek, _Lectures on discrete geometry_ , vol. 212, Springer Science & Business Media, 2013.
  * [10] Brian McDonald, Anurag Sahay, and Emmett L Wyman, _The VC-dimension of quadratic residues in finite fields_ , arXiv preprint arXiv:2210.03789 (2022).
  * [11] Thang Pham, Steven Senger, Michael Tait, and Vu Thi Huong Thu, _Geometric structures in pseudo-random graphs_ , arXiv preprint arXiv:2208.04399 (2022).
  * [12] Le Anh Vinh, _The solvability of norm, bilinear and quadratic equations over finite fields via spectra of graphs_ , Forum mathematicum, vol. 26, Walter de Gruyter GmbH, 2014, pp. 141–175.