# Correlation between entropy and generalizability in a neural network

Ge Zhang  _Department of Physics_ , _City University of Hong Kong_ , Hong
Kong, China

###### Abstract

Although neural networks can solve very complex machine-learning problems, the
theoretical reason for their generalizability is still not fully understood.
Here we use Wang-Landau Mote Carlo algorithm to calculate the entropy
(logarithm of the volume of a part of the parameter space) at a given test
accuracy, and a given training loss function value or training accuracy. Our
results show that entropical forces help generalizability. Although our study
is on a very simple application of neural networks (a spiral dataset and a
small, fully-connected neural network), our approach should be useful in
explaining the generalizability of more complicated neural networks in future
works.

##  I Introduction

Neural networks has gained tremendous success in solving machine-learning
problems since the past decade or so. One remaining challenge in this field,
though, is theoretically understanding their success. Conceptually, many
neural-network applications are similar to fitting. We know that in
traditional polynomial fitting, if the polynomial has too many degrees of
freedom, then it tends to overfit the noise in the data, resulting in poor
predictions. Neural networks contain way more degrees of freedom, so why don’t
they overfit?

The above question is one of the central issue in machine learning, and this
paper certainly does not offer a complete answer. Here we demonstrate that a
statistical-physical approach is valuable when searching for answers. We study
the correlation between the entropy and generalizability when a neural network
well fits a training data set (low training loss or high training accuracy).
Here the entropy is defined as the logarithm of the volume in the high-
dimensional parameter space that correspond to a particular training error,
training loss, or test error. We calculate the entropy using Wang-Landau Monte
Carlo, and show that for a simple machine-learning problem (a fully-connected
neural network applied to the spiral dataset), at zero training error or at a
very low training loss, the entropically-favored states have very high test
accuracies that increases as the network depth increases. Our results suggest
that while parameter choices with serious overfitting problems exist, they
simply have too low entropy to be a probable result after training.

##  II Definitions

In traditional polynomial fitting, one defines a parameterized function, e.g.,

$f(\mathbf{c},x)=c_{1}+c_{2}x+\cdots+c_{N}x^{N-1},$ (1)

where $\mathbf{c}=(c_{1},c_{2},\cdots,c_{N})$ is a vector representation of
the parameters and $x$ is the independent variable; and finds parameters that
fits a dataset. The dataset consists of pairs of values $(x_{i},y_{i})$, where
$i=1,2,\cdots,N_{d}$, $N_{d}$ is the number of data points, and $y_{i}$ are
the expected function value. The parameters are usually found by minimizing a
function that quantifies the difference between the prediction and data, for
example

$L(\mathbf{c})=\sum_{i=1}^{N_{d}}\left[f(\mathbf{c},x_{i})-y_{i}\right]^{2}.$
(2)

$L(\mathbf{c})$ is called the “loss function” in the machine-learning
community.

A neural network is conceptually similar but has the following differences.
First, the function input $\mathbf{x}$ is usually a vector rather than a
scalar. Second, the parameterized funcion is usually way more complicated.
Here we consider a relatively simple case, a fully-connected neural network
with $H$ hidden layers of $W$ neurons. Let $\mathbf{a}_{i}$ be the
intermediate result after the $i$th layer, and let
$\mathbf{a}_{0}=\mathbf{x}$. The dimensionality of
$\mathbf{a}_{1},\mathbf{a}_{2},\cdots,\mathbf{a}_{H}$ are a constant $W$. Both
$\mathbf{a}_{0}$ and $\mathbf{a}_{H+1}$ are two-dimensional vectors in this
paper, in order to suit the problem we will study (detailed later). Each layer
performs the following computation

$\mathbf{a}_{i}=\mbox{RELU}(w_{i}\mathbf{a}_{i-1}+\mathbf{b}_{i}),$ (3)

where $w_{i}$ are matrices, the number of rows and columns of $w_{i}$ are
chosen so that the multiplication with $\mathbf{a}_{i-1}$ produces the desired
dimensionality for $\mathbf{a}_{i}$, $b_{i}$ are vectors, and $\mbox{RELU}()$
function changes each negative component of a vector to zero while leaving the
positive components unchanged. All elements of $w_{i}$ and $b_{i}$ are
considered fitting parameters. In other words, $\mathbf{c}$ is a very long
vector defined as the concatenation of $w_{i}$ and $b_{i}$ for all $i$.

Third, while the prediction from a polynomial fit is a continuous variable,
many neural-network applications desires categorical predictions. In such
case, the most common practice is to append a so-called “softmax layer” to the
neural network

$a_{H+2,i}=\frac{\exp(a_{H+1,i})}{\sum_{i}\exp(a_{H+1,i})}.$ (4)

where $a_{H,i}$ is the $i$th component of vector $\mathbf{a}_{H}$. Since Eq.
(4) guarantees that $\sum_{i}a_{H+2,i}=1$, one can then interpret $a_{H+2,i}$
as the probability that the input belongs to the $i$th category. The accuracy
$A$ is defined as the probability that $a_{H+2,y_{i}}$ is the largest element
of vector $\mathbf{a}_{H+2}$. The loss function, Eq. (2), is also changed to
become suitable for categorical predictions

$L(\mathbf{c})=-\sum_{i}^{N_{d}}\ln{a_{H+2,y_{i}}}.$ (5)

The idea is that for the $i$th data point, since $y_{i}$ is the desired
prediction, the higher $a_{H+2,y_{i}}$ is, the more confident the neural
network is on the correct answer, and the lower $L$ is. Machine-learning
researchers found that adding a so-called “regularization term” to $L$ can
often improve generalization, so we will also try that. The resulting loss
function is

$L(\mathbf{c})=-\sum_{i}^{N_{d}}\ln{a_{H+2,y_{i}}}+\lambda|\mathbf{c}|^{2},$
(6)

where $\lambda$ is a constant called the “regularization parameter.”

The neural network is applied on the so-called “spiral” dataset, one example
is shown in Fig. 1. Black dots and red dots form two arms of a spiral in a 2D
plane. Given the horizontal and vertical coordinates of a dot, the neural
network is asked to predict the color of the dot. More specifically, we
compute the $i$th datapoint with the following formula:

$x_{i}=(r_{i}\cos\theta_{i}+N_{1i},r_{i}\sin\theta_{i}+N_{2i}),$ (7)

where $r_{i}$ is uniformly distributed between 1 and 5, $\theta_{i}=2r_{i}+\pi
y_{i}$, and both $N_{1i}$ and $N_{2i}$ are Gaussian random noises with mean 0
and standard deviation 0.1. We generate 20 random black dots ($y_{i}=0$), and
20 random red dots ($y_{i}=1$). They constitute our training set. We then
generate a test set following exactly the same distribution.

Figure 1: One example of our dataset.

We define the set of all possible choices of $\mathbf{c}$ as the “parameter
space.” The parameter space has an infinite volume, but we will study a
finite-volume region. Machine-learning practitioners found that training the
neural-network is most efficient when each element of the weight matrix is on
the order of $1/\sqrt{W}$. We therefore limit each component of $\mathbf{c}$
to the range $[-2/\sqrt{W},2/\sqrt{W}]$. We will then discuss specific parts
within this region, e.g., the part that correspond to $100\%$ training
accuracy and $90\%$ test accuracy. The entropy for each part of the parameter
space is defined as

$S=\ln(V_{p}/V_{\mbox{all}}),$ (8)

where $V_{p}$ is the volume of this part of the parameter space,
$V_{\mbox{all}}=\left(4/\sqrt{W}\right)^{d}$ is the total volume of the region
of parameter space we are studying, and $d$ is the number of parameters.

##  III Numerical procedure

We use Wang-Landau Monte Carlo [1] to compute such entropies. Our results are
averaged over 6 realizations of the training and test datasets in Sec. IV.1
and 24 realizations of the datasets in Sec. IV.2. For each pair of datasets,
we perform $10^{4}$ stages of Monte Carlo simulation. Each stage contains
$3.2\times 10^{6}$ trial moves. The step sizes of the trial moves are adjusted
on-the-fly so that probability of accepting is between 0.3 and 0.7: after
every 1000 trail moves, the step size is increased or decreased by 10% if the
acceptance rate is too high or too low. The “modification factor” in Ref. [1]
is $f=\exp[5/(n+10)]$, for the $n$th stage.

##  IV Results

###  IV.1 calculating entropy as a function of train loss and test accuracy

We can calculate the entropy as a function of the training loss and the test
accuracy, $S(L_{\mbox{train}},A_{\mbox{test}})$. Results for $H=4$ and $W=8$
are shown in Fig. 2. For each bin of $L_{\mbox{train}}$, we can calculate the
equilibrium test accuracy, i.e., the test accuracy averaged over their weight
determined by the entropy

$\langle
A_{\mbox{test}}(L_{\mbox{train}})\rangle=\frac{\int_{0}^{1}x\exp\left[S(L_{\mbox{train}},x)\right]dx}{\int_{0}^{1}\exp\left[S(L_{\mbox{train}},x)\right]dx}.$
(9)

Such test accuracies are plotted as magenta dots in Fig. 2. We also compare
$\langle A_{\mbox{test}}(L_{\mbox{train}})\rangle$ curves for the cases with
and without regularization. We see that at low train loss values,
regularization indeed raises the test accuracy.

Figure 2: (top) Entropy as a function of the test accuracy and the loss
function on the training dataset without regularization. At each train loss
value, we compute the average test accuracy of an equilibrium state (see main
text for details) and mark it using a magenta dot. (middle) Same as top,
except with regularization parameter $\lambda=10^{-4}$. (bottom) Comparing the
equilibrium test accuracy for the two cases.

Having found the equilibrium test accuracy, we can compare it with the test
accuracy of typically trained neural networks. The comparison is presented in
Table 1. For each set of conditions (each row) we trained 100 instances of the
neural network and presented their average test accuracy here. We train our
neural networks using the “Adam optimizer” [2] with learning rate $10^{-3}$.
We did not divide the training data into batches. For all cases, the trained
neural network possessed test accuracies that are much worse than the
equilibrium state. This shows that a typically trained neural network is in an
non-equilibrium state, with generalization performance worse than the
equilibrium state at the same $L_{\mbox{train}}$.

Table 1: Comparison of the test accuracy of a neural network trained with gradient descent algorithm and the test accuracy of the equilibrium state. $H$ | $W$ |  training time (epochs) | $L_{\mbox{train}}$ |  trained $A_{\mbox{test}}$ |  equilibrium $A_{\mbox{test}}$
---|---|---|---|---|---
3 | 6 | 2000 | 0.152 | 71% | 83%
3 | 8 | 2000 | 0.077 | 73% | 85%
4 | 6 | 2000 | 0.103 | 73% | 84%
4 | 8 | 2000 | 0.045 | 74% | 86%
3 | 6 | 5000 | 0.082 | 74% | 85%
3 | 8 | 5000 | 0.016 | 77% | 87%
4 | 6 | 5000 | 0.012 | 75% | 85%
4 | 8 | 5000 | 0.006 | 78% | 87%

###  IV.2 calculating entropy as a function of train accuracy and test
accuracy

We can also calculate the entropy as a function of the accuracy on the
training and test datasets, $S(A_{\mbox{train}},A_{\mbox{test}})$. We can
study the relation between $S$ and $A_{\mbox{test}}$ when $A_{\mbox{train}}$
is set to be 100%, i.e., when the neural network perfectly fits the training
data. This approach appears to be more straightforward, but we lose the
ability to incorporate regularization into the picture because $S$ no longer
depends on any loss function. Our results are presented in Fig. 3. We see that
when the number of neurons per layer $W$ is fixed, increasing the number of
layers $H$ makes the curve shift to the right. This indicates that as the
neural network becomes deeper, its entropically-favored state gains
generalizability. When we fix $H$ and increase $W$, however, the opposite
happened. Indicating that wider neural networks possess worse entropically-
favored state. The last result is counter-intuitive, and the cause should be
investigated in the future.

Figure 3: Entropy as a function of test accuracy under the constraint that the
training accuracy is 100%. (top) Results for $W=6$ and various $H$. (bottom)
Results for $H=3$ and various $W$.

##  V Discussion

In this paper, we investigated the relationship between entropy and the
training loss function, training accuracy, and test accuracy. We find that an
equilibrium state (roughly speaking, the max-entropy state) of a neural
network possesses a much higher test accuracy than a typically trained state.
We also show that the equilibrium test accuracy increases as the network depth
increases.

We plan to carry out this study for more complicated neural networks and
datasets, e.g., convolutional neural networks on image-classification tasks,
or transformer neural networks on language/reasoning tasks. These networks are
much more computationally intensive, and we plan to change our method to Wang-
Landau molecular dynamics to improve efficiency. This is because molecular-
dynamics-based algorithms gains better efficiency by utilizing the derivative
of the loss function, which is easily available from machine-learning
software.

## References

  * Wang and Landau [2001] F. Wang and D. P. Landau, Efficient, multiple-range random walk algorithm to calculate the density of states, Phys. Rev. Lett. 86, 2050 (2001).
  * Kingma and Ba [2014] D. P. Kingma and J. Ba, Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6980 (2014).


# Approximately Strongly Regular Graphs

Ferdinand Ihringer

(16 May 2022)

###### Abstract

We give variants of the Krein bound and the absolute bound for graphs with a
spectrum similar to that of a strongly regular graph. In particular, we
investigate what we call approximately strongly regular graphs.

We apply our results to extremal problems and show the following:

(1) Caps in $\mathrm{PG}(n,q)$ for which the number of secants on exterior
points does not vary too much, have size at most
$O(q^{\frac{5}{6}n-\frac{1}{6}})$ (as $q\rightarrow\infty$ or as
$n\rightarrow\infty$).

(2) Optimally pseudorandom $K_{m}$-free graphs of order $v$ and degree $k$ for
which the induced subgraph on the common neighborhood of a clique of size
$i\leq m-3$ is similar to a strongly regular graph, have
$k=O(v^{1-\frac{1}{3m-2i-5}})$.

##  1 Introduction

We investigate graphs and families of graphs which asymptotically behave like
strongly regular graphs (SRGs). In particular, we generalize existence
conditions. Our interest stems from the fact that for some extremal problems
such as the cap set problem or optimally pseudorandom clique-free graphs (see
§5) it is natural to look for constructions which behave very similarly to
strongly regular graphs.

All graphs in this document are finite and simple. Let us repeat some basic
facts about strongly regular graphs and bounds on their parameters: Our
notation for strongly regular graphs is standard, cf. [6, 7]. A strongly
regular graph $\Gamma$ with parameters $(v,k,\lambda,\mu)$ is a $k$-regular
graph (not complete, not edgeless) of order $v$ such that two distinct
adjacent vertices have precisely $\lambda$ common neighbors, while two
distinct nonadjacent vertices have precisely $\mu$ common neighbors. One of
the parameters depends on the others: For a fixed vertex $a$, counting the
pairs $(b,c)$ with $a\sim b\sim c\not\sim a$ in two ways shows that
$(v-k-1)\mu=k(k-\lambda-1)$.

Call an eigenvalue of the adjacency matrix of a regular graph restricted if it
has an eigenvector orthogonal to the all-ones vector. Then, alternatively, a
strongly regular graph can be defined as a $k$-regular graph whose adjacency
matrix $A$ has exactly two restricted eigenvalues $r\geq 0$ and $s<0$. Denote
the multiplicity of $r$ by $f$ and the multiplicity of $s$ by $g$. We have the
identities

$\displaystyle\lambda-\mu=r+s,$ $\displaystyle k-\mu=-rs.$

Explicit formulas for $f$ and $g$ can be found using $1+f+g=v$ and
$k+fr+gs=\mathrm{tr}(A)=0$.

The Krein bound111Named somewhat indirectly after Mark Grigorievich Krein, cf.
[7, p. 26]. and the absolute bound provide asymptotic conditions on the
parameters $(v,k,\lambda,\mu)$ of a strongly regular graph.

As a toy example for this introduction, we consider the parameter set
$v=(1+o(1))\lambda^{11}$, $k=(1+o(1))\lambda^{10}$, and
$\mu=(1+o(1))\lambda^{9}$ (as $\lambda\rightarrow\infty$). See §3.1 for a
discussion of big-$O$ (and similar) notation.

######  Theorem 1.1 (Krein Bound for SRGs, [7, p. 26]).

The eigenvalues $k\geq r\geq 0>s$ of a strongly regular graph satisfy

$\displaystyle 1+\frac{s^{3}}{k^{2}}-\frac{(s+1)^{3}}{(v-k-1)^{2}}\geq 0,$
$\displaystyle 1+\frac{r^{3}}{k^{2}}-\frac{(r+1)^{3}}{(v-k-1)^{2}}\geq 0.$

In the toy example above, $s=(-1+o(1))\lambda^{9}$, so Theorem 1.1 implies
$1+(-1+o(1))\lambda^{7}-(1+o(1))\lambda^{5}\geq 0$ which is impossible.

The absolute bound for strongly regular graphs is a corollary of the well-
known result by Delsarte, Goethals, and Seidel that a family of $n$ unit
vector in ${\mathbb{R}}^{d}$ with at most three distinct inner products
satisfies $n\leq\frac{1}{2}d(d+3)$, see Theorem 4.8 and Theorem 4.11 in [9].

######  Theorem 1.2 (Absolute Bound for SRGs, [7, Prop. 1.3.14]).

The multiplicities $f,g$ of a primitive strongly regular graph satisfy
$v\leq\frac{1}{2}f(f+3)$ and $v\leq\frac{1}{2}g(g+3)$.

In the toy example above, $g=(1+o(1))\lambda^{3}$, so Theorem 1.2 implies
$(1+o(1))\lambda^{11}\leq\frac{1}{2}\lambda^{6}$ which is impossible.

In the first part of this document, we generalize Theorem 1.1.

######  Proposition 1.3 (Krein Bound, Variant for Regular Graphs).

Let $\Gamma$ be a $k$-regular graph of order $v$ with adjacency matrix $A$.
Let $r$ denote the second largest and $s$ the smallest eigenvalue of $A$. Then

$\displaystyle(s+r^{2})v+(k-r)(r-s)\geq 0,$
$\displaystyle(r+s^{2})v+(k-s)(s-r)\geq 0.$

There is a poor man’s version of the absolute bound which only shows $v\leq
f^{2}$ and $v\leq g^{2}$. We give a variant of this poor man’s result.

######  Proposition 1.4 (Absolute Bound, Variant).

Consider a $k$-regular graph of order $v$ with adjacency matrix $A$. Let $r,s$
be real numbers with $k>r\geq 0>s$. Suppose that $A$ has at least $f_{1}$ and
at most $f_{2}$ restricted eigenvalues in $[r,k]$, all eigenvalues of $A$ are
at least $s-\varepsilon$ for some $\varepsilon>0$, and at least $v-f_{2}$
eigenvalues of $A$ are in $[s-\varepsilon,s]$. If $s^{2}+s>\varepsilon$, then
$v\leq f_{2}(f_{2}+1)-f_{1}$.

In the second part of this document, we consider what we call approximately
strongly regular graphs. For two adjacent vertices $a$ and $b$ of a graph
$\Gamma$, let $\lambda_{ab}$ denote the number of common neighbors of $a$ and
$b$ in $\Gamma$. Similarly, for two distinct nonadjacent vertices $a$ and $b$
of a graph $\Gamma$, let $\mu_{ab}$ denote the number of common neighbors of
$a$ and $b$ in $\Gamma$. Let $\Lambda$ (respectively, $M$) denote the set of
all pairs of adjacent (respectively, distinct nonadjacent) vertices in
$\Gamma$.

We call a $k$-regular graph (not complete, not edgeless) $\Gamma$ of order $v$
an approximately strongly regular graph with parameters
$(v,k,\lambda,\mu;\sigma)$, where $\sigma\geq 0$, if
${\mathbb{E}}(\lambda_{ab})\coloneq\frac{1}{|\Lambda|}\sum_{(a,b)\in\Lambda}\lambda_{ab}=\lambda$
and
$\mathrm{Var}(\lambda_{ab})\coloneq\frac{1}{|\Lambda|}\sum_{(a,b)\in\Lambda}(\lambda_{ab}-\lambda)^{2}\leq\sigma^{2}$,
and ${\mathbb{E}}(\mu_{ab})\coloneq\frac{1}{|M|}\sum_{(a,b)\in M}\mu_{ab}=\mu$
and $\mathrm{Var}(\mu_{ab})\coloneq\frac{1}{|M|}\sum_{(a,b)\in
M}(\mu_{ab}-\mu)^{2}\leq\sigma^{2}$.

Strongly regular graphs are precisely the approximately strongly regular
graphs with $\sigma=0$. The complement of an approximately strongly regular
graph with parameters $(v,k,\lambda,\mu;\sigma)$ is an approximately strongly
regular graph with parameters $(v,v-k-1,v-2k+\mu,v-2k+\lambda;\sigma)$.
Counting triples $(a,b,c)$ with $a\sim b\sim c\not\sim a$ shows
$\sum_{(a,c)\in M}\mu_{ac}=\sum_{(a,b)\in\Lambda}(k-\lambda_{ab}-1)$. Hence,
$(v-k-1)\mu=k(k-\lambda-1)$ also holds for approximately strongly regular
graphs.

In our toy example with $v=(1+o(1))\lambda^{11}$, $k=(1+o(1))\lambda^{10}$,
and $\mu=(1+o(1))\lambda^{9}$, we will see that Proposition 1.3 rules out the
existence of approximately strongly regular graphs with
$\sigma=o(\lambda^{2.5})$.

In the third part of this document, we apply our results to the cap set
problem and to optimally pseudorandom clique-free graphs.

For instance, if there exists a cap of size $(1+o(1))q^{9}$ in the projective
space $\mathrm{PG}(10,q)$, then a standard construction yields a approximately
strongly regular graph with the same parameters of our toy example (where
$\lambda=q-2$).

##  2 Proofs of Bounds

Denote the all-ones vector by $j$, the all-ones matrix by $J$, and the
identity matrix by $I$.

###  2.1 Krein Bounds

The following proof is based on Remark (i) on page 50 in [6].

###### Proof of Proposition 3.4.

Consider the matrices $E_{1}$ and $E_{2}$ defined by

$\displaystyle E_{1}=\frac{1}{r-s}\left(A-sI-\tfrac{k-s}{v}J\right),$
$\displaystyle E_{2}=\frac{1}{s-r}\left(A-rI-\tfrac{k-r}{v}J\right).$

The spectrum of $E_{2}$ is in $[0,1]$ as $(s-r)E_{2}$ has only eigenvalues in
$[s,r]$. Write $E_{2}\circ E_{2}$ as a linear combination of the matrices
$A,I,J$. Then the coefficients of $I$ and $A$ are

$\displaystyle\frac{1}{(s-r)^{2}}\left(r^{2}+r\tfrac{k-r}{v}\right)\text{ for
}I,$ $\displaystyle\frac{1}{(s-r)^{2}}\left(1-\tfrac{k-r}{v}\right)$
$\displaystyle\text{ for }A.$

Now we write $E_{2}\circ E_{2}$ as a linear combination of the matrices
$E_{1},E_{2},J$, that is we replace $A$ and $I$ by $E_{1}$ and $E_{2}$. We
obtain the coefficients

$\displaystyle\frac{r+r^{2}}{(s-r)^{2}}\text{ for $E_{1}$, }$ $\displaystyle
t\coloneq\frac{(s+r^{2})v+(k-r)(r-s)}{v(s-r)^{2}}\text{ for $E_{2}$}.$

Let $\chi$ be an eigenvector of $A$ with $A\chi=s\chi$. Then $E_{1}\chi=0$.
Hence, $(E_{2}\circ E_{2})\chi=tE_{2}\chi=t\chi$. Hence, $\chi$ is an
eigenvector of $E_{2}\circ E_{2}$ which shows that $t\geq 0$. Hence, using our
expression for $\beta$ and $u_{i}-r<u_{i}$, we obtain the first inequality.

For the second inequality, consider $E_{1}\circ E_{1}$ instead of $E_{2}\circ
E_{2}$. ∎

###  2.2 Absolute Bounds

The following is based on the proof of Theorem 2.3.3 in [6]. We use eigenvalue
interlacing (cf. [13]). More precisely, if $A$ is a real symmetric matrix of
order $v$ with eigenvalues $u_{1}\geq\ldots\geq u_{v}$ and $B$ is a principal
submatrix of $A$ of order $w$ with eigenvalues $\nu_{1}\geq\ldots\geq\nu_{w}$,
then $u_{i}\geq\nu_{i}\geq u_{i-w+v}$.

###### Proof of Proposition 1.4.

Consider $M\coloneq A-sI-\frac{k-s}{v}J$. Then $M$ has at least $v-f_{2}$
eigenvalues in $[-\varepsilon,0]$, and between $f_{1}$ and $f_{2}$ eigenvalues
at least $r-s$. Hence, $M\otimes M$ has at most $f_{2}^{2}$ eigenvalues at
least $(r-s)^{2}$, while all its other eigenvalues are at most
$\varepsilon^{2}$. Furthermore,

$M\circ
M=(1-\tfrac{k-s}{v})A+\left(s^{2}+s\tfrac{k-s}{v}\right)I+\left(\tfrac{k-s}{v}\right)^{2}J.$

Hence, $M\circ M$ has one eigenvalue
$(k-k\frac{k-s}{v})+(s^{2}+s\frac{k-s}{v})+\left(\frac{k-s}{v}\right)^{2}v\geq
s^{2}+s$ with eigenvector $j$, at least $f_{1}$ eigenvalues at least
$(r-r\frac{k-s}{v})+(s^{2}+s\frac{k-s}{v})\geq s^{2}+s$ and at least $v-f_{2}$
eigenvalues at least $(s-s\frac{k-s}{v})+(s^{2}+s\frac{k-s}{v})=s^{2}+s$. The
matrix $M\circ M$ is a principal submatrix of $M\otimes M$, so the eigenvalues
of $M\circ M$ interlace those of $M\otimes M$. Hence, $M\circ M$ has at most
$f_{2}^{2}$ eigenvalues greater than $\varepsilon^{2}<s^{2}+s$. We obtain that
$v-f_{2}+f_{1}\leq f_{2}^{2}$. ∎

##  3 Approximately Strongly Regular Graphs

Consider the adjacency matrix $A$ of an approximately strongly regular graph
$\Gamma$ with parameters $(v,k,\lambda,\mu;\sigma)$. We can write
$A^{2}=kI+\lambda A+\mu(J-I-A)+E$, where $(E)_{ab}=\lambda_{ab}-\lambda$ when
$a,b$ are adjacent, $(E)_{ab}=\mu_{ab}-\mu$ when $a,b$ are distinct and
nonadjacent, and $(E)_{ab}=0$ when $a=b$.

Let $\chi$ be an eigenvector of $A$ orthogonal to the all-ones vector $j$ with
eigenvalue $u$. Then
$u^{2}\chi=A^{2}\chi=(k-\mu)\chi+(\lambda-\mu)u\chi+E\chi$. Hence, $\chi$ is
an eigenvector of $E$ with some eigenvalue $\nu$. By solving for $u$, we find
that

$u=\frac{1}{2}\left((\lambda-\mu)\pm\sqrt{(\lambda-\mu)^{2}+4(k-\mu+\nu)}\right).$

We say that $u$ has positive form if

$u=\frac{1}{2}\left((\lambda-\mu)+\sqrt{(\lambda-\mu)^{2}+4(k-\mu+\nu)}\right),$

and that $u$ has negative form if

$u=\frac{1}{2}\left((\lambda-\mu)-\sqrt{(\lambda-\mu)^{2}+4(k-\mu+\nu)}\right).$

Let $u_{1},u_{2},\ldots,u_{v}$ denote the eigenvalues of $A$. For $u_{i}$ an
eigenvalue of $A$, let $\nu_{i}$ denote the corresponding eigenvalue of $E$.

The next result shows that if $\sigma$ and $v$ are sufficiently small, then
there are few large $\nu_{i}$.

######  Lemma 3.1.

The eigenvalues $\nu_{1},\ldots,\nu_{v}$ of $E$ satisfy $\sum\nu_{i}^{2}\leq
v(v-1)\sigma^{2}$.

###### Proof.

We have

$\sum\nu_{i}^{2}=\mathrm{tr}(E^{2})=\sum_{a\sim
b}(\lambda_{ab}-\lambda)^{2}+\sum_{a\not\sim b}(\mu_{ab}-\mu)^{2}\leq
v(v-1)\sigma^{2}.\qed$

###  3.1 Big-$O$ Notation

We use the symbols $O,\Omega,\Theta,o,\omega$ in the following way:

$\displaystyle f(x)=O(g(x))\text{ (as $x\rightarrow a$)}$ if and only if
$\displaystyle\limsup_{x\rightarrow a}\tfrac{|f(x)|}{g(x)}<\infty,$
$\displaystyle f(x)=\Omega(g(x))\text{ (as $x\rightarrow a$)}$ if and only if
$\displaystyle\limsup_{x\rightarrow a}\tfrac{|f(x)|}{g(x)}>0,$ $\displaystyle
f(x)=\Theta(g(x))\text{ (as $x\rightarrow a$)}$ if and only if $\displaystyle
0<\limsup_{x\rightarrow a}\tfrac{|f(x)|}{g(x)}<\infty,$ $\displaystyle
f(x)=o(g(x))\text{ (as $x\rightarrow a$)}$ if and only if
$\displaystyle\lim_{x\rightarrow a}\tfrac{|f(x)|}{g(x)}=0,$ $\displaystyle
f(x)=\omega(g(x))\text{ (as $x\rightarrow a$)}$ if and only if
$\displaystyle\lim_{x\rightarrow a}\tfrac{|f(x)|}{g(x)}=\infty.$

Usually, we have $a=\infty$. If there are several variables involved, then we
specify the relevant one. We also use the big-$O$ notation in minor order
terms. For instance, we can write $x^{2}+x+100=x^{2}+O(x)$ (as
$x\rightarrow\infty$) as $x+100=O(x)$. For us the sign of $f(x)$ is often
important, so for convenience, we aim to use big-$O$ notation with $f(x)>0$.
For instance, we write $-s=O(\mu)$ even though $s=O(\mu)$ is equally correct.

If we talk about a $k$-regular graph $\Gamma$ of order $v$ with $k=O(g(v))$
for some function $g$, then we mean that we consider an infinite family of
graphs $(\Gamma_{n})$, where $\Gamma_{n}$ is of order $v_{n}$ and
$k_{n}$-regular with $k_{n}=O(g(v_{n}))$ as $n\rightarrow\infty$. In
particular, if we say that $\Gamma$ is an approximately strongly regular graph
or a family of approximately strongly regular graphs with parameters
$(v,k,\lambda,\mu;\sigma)$ and $k=o(|\mu-\lambda|^{\frac{3}{2}})$, then there
is an infinite family of approximately strongly regular graphs $(\Gamma_{n})$
with parameters $(v_{n},k_{n},\lambda_{n},\mu_{n};\sigma_{n})$ such that
$k_{n}=o(|\mu_{n}-\lambda_{n}|^{\frac{3}{2}})$ as $n\rightarrow\infty$.

We also use big-$O$ notation for the eigenvalues $u_{i}$ and $\nu_{i}$: Assume
that $|\nu_{1}|\geq|\nu_{2}|\geq\cdots\geq|\nu_{v}|$. If we write
$\nu_{i}=O(g(n))$, then there is a function $h(n)$ such that
$\nu_{h(n)}=O(g(n))$. For instance, we might assume that $\nu_{i}=O(\mu_{n})$
and show some property (P) for $\nu_{i}$. By Lemma 3.1, $\sum\nu_{i}^{2}\leq
v^{2}\sigma^{2}$, so the number of $\nu_{i}$ with $\nu_{i}=\omega(\mu)$ is at
most $o(\frac{v\sigma}{\mu})$. Thus, (P) holds for $\nu_{h(n)}$ with
$h(n)=\Omega(\frac{v_{n}\sigma_{n}}{\mu_{n}})$.

###  3.2 Asymptotic Bounds on Eigenvalues

######  Lemma 3.2.

Let $f:{\mathbb{R}}\rightarrow{\mathbb{R}}$ with $f(y)=o(y^{2})$ (as
$y\rightarrow\infty$). Then

$\displaystyle\sqrt{y^{2}+f(y)}-y=(\tfrac{1}{2}+o(1))\tfrac{f(y)}{y}.$

###### Proof.

Write $\sqrt{y^{2}+f(y)}-y=y(\sqrt{1+\frac{f(y)}{y^{2}}}-1)$. The Taylor
expansion of $\sqrt{\cdot}$ at $1$ shows that (as $x\rightarrow 0$)

$\sqrt{1+x}=1+\tfrac{1}{2}x+O(x^{2}).\qed$

The following gives us approximate versions of the equations $\mu-\lambda=r+s$
and $k-\mu=-rs$ for strongly regular graphs.

######  Lemma 3.3.

For a family of approximately strongly regular graphs with parameters
$(v,k,\lambda,\mu;\sigma)$, consider an eigenvalue $u_{i}$ with associated
eigenvalue $\nu_{i}$.

If $\mu>\lambda$, $k=o(|\lambda-\mu|^{2})$, and
$|\nu_{i}|=o(|\lambda-\mu|^{2})$, then the following holds:

  1. (i)

If $u_{i}$ has positive form, then
$u_{i}=(1+o(1))\frac{k-\mu+\nu_{i}}{\mu-\lambda}$.

  2. (ii)

If $u_{i}$ has negative form, then $u_{i}=-(1+o(1))(\mu-\lambda)$.

If $\mu<\lambda$, $k=o(|\lambda-\mu|^{2})$, and
$|\nu_{i}|=o(|\lambda-\mu|^{2})$, then the following holds:

  1. (iii)

If $u_{i}$ has positive form, then $u_{i}=(1+o(1))(\lambda-\mu)$.

  2. (iv)

If $u_{i}$ has negative form, then
$u_{i}=-(1+o(1))\frac{k-\mu+\nu_{i}}{\lambda-\mu}$.

If $k=\Omega(|\lambda-\mu|^{2})$ and $|\nu_{i}|=O(k)$, then the following
holds:

  1. (v)

If $u_{i}$ has positive form, then $u_{i}=\Theta(\sqrt{k})$.

If $|\nu_{i}|=\Omega(|\lambda-\mu|^{2})$ and $|\nu_{i}|=\Omega(k)$, then the
following holds:

  1. (vi)

If $u_{i}$ has positive form, then $u_{i}=\Theta(\sqrt{|\nu_{i}|})$.

###### Proof.

We only show (i) and (ii) as the other cases are similar. Using Lemma 3.2 with
$y=\mu-\lambda$ and $\mu=o(k)$, we find that if $u_{i}$ has positive form,
then

$\displaystyle u_{i}$
$\displaystyle=\tfrac{1}{2}\left(\lambda-\mu+(1+o(1))\sqrt{(\lambda-\mu)^{2}-4(k-\mu+\nu_{i})}\right)$
$\displaystyle=(1+o(1))\tfrac{k-\mu+\nu_{i}}{\mu-\lambda}.$

If $u_{i}$ has negative form, then

$\displaystyle u_{i}$
$\displaystyle=\tfrac{1}{2}\left(\lambda-\mu-(1+o(1))\sqrt{(\lambda-\mu)^{2}-4(k-\mu+\nu_{i})}\right)$
$\displaystyle=-(1+o(1))(\mu-\lambda).\qed$

###  3.3 Parameter Restrictions

The expected size of the common neighborhood of two distinct vertices is
$(1+o(1))\frac{k^{2}}{v}$. Hence, if $k=o(v)$, then
$\mu=(1+o(1))\frac{k^{2}}{v}$.

######  Proposition 3.4 (Krein Bound, Approximately Strongly Regular Graphs).

Consider a family of approximately strongly regular graphs with $\mu>\lambda$,
$k=o(v)$, and $k=o(|\mu-\lambda|^{\frac{3}{2}})$. Then
$\sigma\geq(1+o(1))\frac{|\mu-\lambda|^{\frac{3}{2}}}{v}$.

###### Proof.

Suppose to the contrary that
$\sigma\leq(D+o(1))\frac{(\mu-\lambda)^{\frac{3}{2}}}{v}$ for some constant
$D<1$. By Lemma 3.1, $\nu_{i}\leq(D+o(1))(\mu-\lambda)^{\frac{3}{2}}$ for an
eigenvalue $\nu_{i}$ of $E$. Let $u_{i}$ be an eigenvalue of $A$. By Lemma 3.3
(i), if $u_{i}$ has positive form, then

$\displaystyle u_{i}$
$\displaystyle=(1+o(1))\left(\tfrac{k-\mu}{\mu-\lambda}+D\sqrt{\mu-\lambda}\right)=(D+o(1))\sqrt{\mu-\lambda}\eqcolon
r.$

By Lemma 3.3 (ii), if $u_{i}$ has negative form, then

$\displaystyle u_{i}$ $\displaystyle=-(1+o(1))(\mu-\lambda)\eqcolon s.$

Hence, $r^{2}=-(D^{2}+o(1))s$. By Proposition 1.3,

$\displaystyle 0$ $\displaystyle\leq(s+r^{2})v+(k-r)(r-s)$
$\displaystyle=(1-D^{2}+o(1))sv-sk=(1-D^{2}+o(1))sv<0.$

This is a contradiction, so $\sigma\geq(1+o(1))|\mu-\lambda|^{\frac{3}{2}}$. ∎

######  Proposition 3.5 (Absolute Bound, Approximately Strongly Regular
Graphs).

Consider a family of approximately strongly regular graphs such that
$\lambda>\mu$ and $\sqrt{v}\cdot k=o((\lambda-\mu)^{2})$. Then
$\sigma\geq(\tfrac{1}{3}+o(1))\frac{k}{v}$.

###### Proof.

Our plan for applying Proposition 1.4 is as follows: We can ignore $f_{1}$ as
it is a minor order term. We suppose that $\sigma\leq(D+o(1))\frac{k}{v}$ for
some constant $D<\frac{1}{3}$. Put $r=(1+o(1))(\lambda-\mu)$,
$s=-(1-D+o(1))\frac{k-\mu}{\lambda-\mu}$, and
$\varepsilon=(2D+o(1))\frac{k-\mu}{\lambda-\mu}$. As $D<\frac{1}{3}$, we have
that $s^{2}+s>\varepsilon^{2}$.

By Lemma 3.1, any $\nu_{i}$ satisfies $|\nu_{i}|\leq v\sigma\leq(D+o(1))k$. If
an eigenvalue $u_{i}$ has positive form, then, by Lemma 3.3 (iii),

$\displaystyle u_{i}=(1+o(1))(\lambda-\mu)=r.$

If an eigenvalue $u_{i}$ has negative form, then, by Lemma 3.3 (iv),

$\displaystyle s-\varepsilon=-(1+o(1))\tfrac{k-\mu+Dk}{\lambda-\mu}\leq
u_{i}\leq-(1+o(1))\tfrac{k-\mu-Dk}{\lambda-\mu}=s.$

To apply Proposition 1.4, it remains to determine $f_{2}$, that is we need to
bound the number of restricted eigenvalues in $[r,k]$. We already saw that all
such $u_{i}$ are of positive form. Using $\sum
u_{i}^{2}=\mathrm{tr}(A^{2})=vk$, we see that there are at most
$(1+o(1))\frac{vk}{(\lambda-\mu)^{2}}$ eigenvalues $u_{i}$ of positive form in
this interval. Using $\sqrt{v}\cdot k=o((\lambda-\mu)^{2})$, we see
$\frac{vk}{(\lambda-\mu)^{2}}=o(\sqrt{v})$. ∎

For instance, for $v=(1+o(1))q^{11}$, $k=(1+o(1))q^{9}$,
$\lambda=(1+o(1))q^{8}$, and $\mu=(1+o(1))q^{7}$, Proposition 3.5 shows
$\sigma\geq(\tfrac{1}{3}+o(1))q^{-2}$.

##  4 One Example: Orthogonality Graphs

Clearly, strongly regular graphs provide plenty of examples for approximately
strongly regular graphs with $\sigma=0$. For our application in §5.2, we want
to present one naturally occurring example with small, but nonzero $\sigma$.

For $q$ an odd prime power, let $V$ be the $n$-dimensional vector spaces over
${\mathbb{F}}_{q}$, the finite field with $q$ elements. As $q$ is odd,
${\mathbb{F}}_{q}$ contains $\frac{q-1}{2}$ (nonzero) squares and
$\frac{q-1}{2}$ nonsquares. Put $\gamma=1$ if $q\equiv 1\pmod{4}$ and
$\gamma=-1$ if $q\equiv 3\pmod{4}$.

A quadratic form over ${\mathbb{F}}_{q}$ is a map
$Q:V\rightarrow{\mathbb{F}}_{q}$ such that $Q(\alpha v)=\alpha^{2}Q(x)$ for
all $\alpha\in{\mathbb{F}}_{q}$ and $x\in V$ and the function $B(x,y)\coloneq
Q(x+y)-Q(x)-Q(y)$ is bilinear. We can find an $(n\times n)$-matrix $M$ such
that $Q(x)=x^{T}Mx$. We say that $Q$ is nondegenerate if
$\det(Q)\coloneq\det(M)\neq 0$. From now on we assume that $Q$ is
nondegenerate. For $x\in V$ nonzero, call $\langle x\rangle$ a point. Call a
point $\langle x\rangle$ singular when $Q(x)=0$. We refer to §2 and §3 in [7]
and §11 in [17] for some background on quadratic forms.

If $n=2m+1$ is odd, then there is only one choice for $Q$ up to isomorphism.
The set of nonsingular points $\langle x\rangle$ splits into two parts of
sizes $\frac{1}{2}q^{m}(q^{m}+\varepsilon)$ for $\varepsilon\in\\{-1,1\\}$.
Here $\varepsilon$ depends on $Q(x)$ being a (nonzero) square or a nonsquare.
Let $NO^{\varepsilon\perp}_{n,q}$ denote the graph with one of the parts as
vertices, two vertices $x,y$ adjacent when they are orthogonal, that is
$B(x,y)=0$. We identify $\varepsilon=1$ with $+$ and $\varepsilon=-1$ with
$-$, so we write $NO^{+\perp}_{n,q}$ and $NO^{-\perp}_{n,q}$. In [7] these
graphs are called $NO^{\varepsilon\perp}_{n}(q)$ for $q\in\\{3,5\\}$.

The automorphism group of $NO^{\varepsilon\perp}_{n,q}$ acts transitively on
cliques of a given size as the corresponding orthogonal group acts
transitively on tuples of pairwise orthogonal points of the same type. A
$k$-regular graph $\Gamma$ of order $v$ is edge-regular with parameters
$(v,k,\lambda)$ if each pair of adjacent vertices lies in exactly $\lambda$
triangles. In particular, $NO^{\varepsilon\perp}_{n,q}$ is edge-regular with
parameters

$\displaystyle v=\tfrac{1}{2}q^{m}(q^{m}+\varepsilon),$ $\displaystyle
k=\tfrac{1}{2}q^{m-1}(q^{m}-\varepsilon),$
$\displaystyle\lambda=\tfrac{1}{2}q^{m-1}(q^{m-1}+\gamma\varepsilon).$

For $q=3,5$, the graph $NO^{\varepsilon\perp}_{n,q}$ is strongly regular with
$\mu=\frac{1}{2}q^{m-1}(q^{m-1}-\varepsilon)$. Standard counting for quadratic
forms shows that

$\displaystyle\tfrac{1}{2}q^{m-1}(q^{m-1}-1)\leq\mu_{xy}\leq\tfrac{1}{2}q^{m-1}(q^{m-1}+1).$

Hence, for fixed $n$ and $q\rightarrow\infty$, the graph
$NO^{\varepsilon\perp}_{n,q}$ is approximately strongly regular with
$\sigma\leq(1+o(1))q^{m-1}$.

If $n=2m$ is even, then there are two choices for $Q$ up to isomorphism,
depending on if $Q$ is of elliptic (put $\varepsilon=-1$) or hyperbolic type
(put $\varepsilon=1$). We can distinguish them by the number of singular
points which is $\frac{(q^{m-1}+\varepsilon)(q^{m}-\varepsilon)}{q-1}$. We can
also distinguish them by $\det(Q)$ being a (nonzero) square or a nonsquare.
The nonsingular points $\langle x\rangle$ split into two orbits of equal size
$\frac{1}{2}q^{m-1}(q^{m}-\varepsilon)$ each, depending on $Q(x)$ being a
square or a nonsquare. Let $NO^{\varepsilon\perp}_{n,q}$ denote the graph with
one of the parts as vertices, two vertices adjacent when orthogonal, that is
$B(x,y)=0$. In [7] these graphs are called $NO^{\varepsilon}_{n}(q)$ for
$q=3$.

As for $n$ odd, the automorphism group of $NO^{\varepsilon\perp}_{n,q}$ acts
transitively on cliques. In particular, it is edge-regular with parameters

$\displaystyle v=\tfrac{1}{2}q^{m-1}(q^{m}-\varepsilon),$ $\displaystyle
k=\tfrac{1}{2}q^{m-1}(q^{m-1}-\gamma\varepsilon),$
$\displaystyle\lambda=\tfrac{1}{2}q^{m-2}(q^{m-1}+\gamma\varepsilon).$

For $q=3$, the graph $NO^{\varepsilon\perp}_{n,q}$ is strongly regular with
$\mu=\frac{1}{2}q^{m-1}(q^{m-2}+\varepsilon)$. Standard counting for quadratic
forms shows that

$\displaystyle\tfrac{1}{2}q^{m-1}(q^{m-2}-1)\leq\mu_{xy}\leq\tfrac{1}{2}q^{m-1}(q^{m-2}+1).$

Hence, for fixed $n$ and $q\rightarrow\infty$, the graph
$NO^{\varepsilon\perp}_{n,q}$ is approximately strongly regular with
$\sigma\leq(1+o(1))q^{m-1}$.

There is the following tower of graphs (see [7, p. 89] for the case $q=3$):
Let $NO^{\varepsilon\perp}_{n,q}(x)$ denote the induced subgraph on the
neighborhood of $x$ in $NO^{\varepsilon\perp}_{n,q}$. We find that
$NO^{\varepsilon\perp}_{2m+1,q}(x)$ is isomorphic to
$NO^{\varepsilon\perp}_{2m,q}$, and that $NO^{\varepsilon\perp}_{2m,q}(x)$ is
isomorphic to $NO^{\gamma\varepsilon\perp}_{2m-1,q}$. The graph
$NO^{+\perp}_{2,q}$ is edgeless if $\gamma=-1$, otherwise it is the union of
$\frac{q-1}{4}$ pairwise disjoint edges. The graph $NO^{-\perp}_{2,q}$ is
edgeless if $\gamma=1$, otherwise it is the union of $\frac{q+1}{4}$ pairwise
disjoint edges. By induction, we find that the clique number of
$NO^{\varepsilon\perp}_{n,q}$ for $n=2m+1$ or $n=2m$ is $n-1$ if
$\gamma\varepsilon=(-1)^{m}$ and $n$ if $\gamma\varepsilon=-(-1)^{m}$.

##  5 Some Applications

###  5.1 Large Caps

Let $n\geq 2$ and let $q$ be a prime power. Consider a set of points
${\mathcal{C}}$ in $\mathrm{PG}(n,q)$, the $n$-dimensional projective space
over ${\mathbb{F}}_{q}$. We use that the number of points in
$\mathrm{PG}(n,q)$ is $\frac{q^{n+1}-1}{q-1}$. If no three points in
${\mathcal{C}}$ are collinear, then ${\mathcal{C}}$ is called a cap.

For the regime of $q=3$ and $n\rightarrow\infty$, the cap set problem recently
gained much prominence due to the breakthrough result by Ellenberg and
Gijswijt, see [12]. Here we consider the regimes where $n$ is fixed and
$q\rightarrow\infty$ as well as where $q$ is fixed and $n\rightarrow\infty$.
Note that [12] considers caps in ${\mathbb{F}}_{q}^{n}$, not
$\mathrm{PG}(n,q)$, but this only changes bounds by constant factor. We always
assume that $q\geq 3$ as $q=2$ is trivial. As the calculations for $n$ fixed
require slightly more care than those for $q$ fixed (but are essentially
identical), we will only include those. It is easy to see that a cap has size
at most $(1+o(1))q^{n-1}$ for $n$ fixed and $q\rightarrow\infty$. The largest
known constructions for caps have size
$\Theta(q^{\lfloor\frac{2}{3}n\rfloor})$. This is tight for $n=2,3$. See [10,
11] for constructions of caps for large $n$ or large $q$.

It is well-known that caps define graphs in various ways. For a cap
${\mathcal{C}}$ of $\mathrm{PG}(n,q)$, define an associated graph $\Gamma$ as
follows: Consider ${\mathbb{F}}_{q}^{n+1}$ with $\mathrm{PG}(n,q)$ as
hyperplane at infinity. Take the vectors of ${\mathbb{F}}_{q}^{n+1}$ as
vertices, two distinct $a,b\in{\mathbb{F}}_{q}^{n+1}$ adjacent if $\langle
a,b\rangle$ meets $\mathrm{PG}(n,q)$ in a point of ${\mathcal{C}}$. Put
$t=|{\mathcal{C}}|$. It is well-known and easy to verify that this defines an
edge-regular graph with $(v,k,\lambda)=(q^{n+1},t(q-1),q-2)$. An exterior
point of ${\mathcal{C}}$ is a point of $\mathrm{PG}(n,q)$ not in
${\mathcal{C}}$ and a secant of ${\mathcal{C}}$ is a line of
$\mathrm{PG}(n,q)$ which meets ${\mathcal{C}}$ in precisely two points.

If each exterior point lies on precisely the same number $h$ of secants, then
we obtain a strongly regular graph with
$\mu=\frac{t(t-1)(q-1)^{2}}{q^{n+1}-1}$. See §8.7.1(vi) in [7]. We can say the
following about this case.

######  Lemma 5.1.

Let ${\mathcal{C}}$ be a cap of size $t$ in $\mathrm{PG}(n,q)$ such that each
exterior point lies on a constant number of secants. Then

$\displaystyle t\leq(1+o(1))q^{\frac{3}{4}n-\frac{1}{4}}$
$\displaystyle(\text{as }q\rightarrow\infty),$ $\displaystyle
t=O(q^{\frac{3}{4}n})$ $\displaystyle(\text{as }n\rightarrow\infty).$

###### Proof.

We only prove the first part. Let us calculate the negative eigenvalue $s<0$
of the associated graph $\Gamma$. We find $s=-(1+o(1))\mu$. One of the Krein
conditions, Theorem 1.1, requires

$\displaystyle 0$ $\displaystyle\leq
1+\frac{s^{3}}{k^{2}}-\frac{(s+1)^{3}}{(v-k-1)^{2}}$
$\displaystyle=1-(1+o(1))\frac{(t^{2}q^{-n+1})^{3}}{(tq)^{2}}=1-(1+o(1))\frac{t^{4}}{q^{3n-1}}.$

Hence, $t\leq(1+o(1))q^{\frac{3}{4}n-\frac{1}{4}}$. ∎

How much can we weaken the condition on the exterior points and secants? From
now on let $h$ be the expected number of secants through an exterior point $p$
of $\mathrm{PG}(n,q)$ and let $h_{p}$ the actual number of secants through
$p$.

######  Lemma 5.2.

Let ${\mathcal{C}}$ be a cap of size $t$ in $\mathrm{PG}(n,q)$ with an
associated approximately strongly regular graph $\Gamma$ with parameters
$(v,k,\lambda,\mu;\sigma)$. Then

$\displaystyle\mathrm{Var}(h_{p})=(\tfrac{1}{4}+o(1))\mathrm{Var}(\mu_{ab})$
$\displaystyle(\text{as }q\rightarrow\infty),$
$\displaystyle\mathrm{Var}(h_{p})=\Theta(\mathrm{Var}(\mu_{ab}))$
$\displaystyle(\text{as }n\rightarrow\infty).$

###### Proof.

We only show the assertion for $q\rightarrow\infty$. Let $M$ be as in the
introduction and let ${\mathcal{D}}$ denote the set of exterior points of
${\mathcal{C}}$. Note that $|M|=q^{2n+2}$ and that
$|{\mathcal{C}}|=O(q^{n-1})$ implies that $|{\mathcal{D}}|=(1+o(1))q^{n}$. If
for two distinct nonadjacent vertices $a,b$ the line $\langle a,b\rangle$
meets ${\mathcal{D}}$ in $p$, then $2h_{p}$ is the number of common neighbors
of $a$ and $b$. Hence,

$\displaystyle\mathrm{Var}(\mu_{ab})$
$\displaystyle=\frac{1}{M}\sum_{a\not\sim
b}(\mu_{ab}-\mu)^{2}=\frac{1}{M}\sum_{p\in{\mathcal{D}}}\sum_{\begin{subarray}{c}a\not\sim
b,\\\ \langle
a,b\rangle\cap\mathrm{PG}(n,q)=p\end{subarray}}(\mu_{ab}-\mu)^{2}$
$\displaystyle=\frac{1}{M}\sum_{p\in{\mathcal{D}}}4\cdot
q^{n+1}(q-2)\cdot(h_{p}-h)^{2}=(4+o(1))q^{-n}\sum_{p\in{\mathcal{D}}}(h_{p}-h)^{2}$
$\displaystyle=(4+o(1))\frac{1}{|{\mathcal{D}}|}\sum_{p\in{\mathcal{D}}}(h_{p}-h)^{2}=(4+o(1))\mathrm{Var}(h_{p}).\qed$

######  Proposition 5.3.

For $n\geq 4$, let ${\mathcal{C}}$ be a cap of size
$t=\Omega(q^{\frac{5}{6}n-\frac{1}{6}})$ in $\mathrm{PG}(n,q)$ and let
${\mathcal{D}}$ denote its exterior points.

  1. (i)

If $\mathrm{Var}(h_{p})\leq(\frac{1}{4}+o(1))\sigma^{2}$, then
$\sigma\geq(1+o(1))t^{3}q^{-\frac{5}{2}n+\frac{1}{2}}$ (as
$q\rightarrow\infty$).

  2. (ii)

If $\mathrm{Var}(h_{p})=\Theta(\sigma^{2})$, then
$\sigma=\Omega(t^{3}q^{-\frac{5}{2}n})$ (as $n\rightarrow\infty$).

###### Proof.

We only prove the first part. By Lemma 5.2, $\sigma$ is as in Proposition 3.4
for the associated graph $\Gamma$. From
$t=\omega(q^{\frac{3}{4}n-\frac{1}{4}})$ and $n\geq 4$, we obtain
$k=(q-1)t=o(\mu^{\frac{3}{2}})$ and $\lambda=q-2=o(\mu)$ (as
$\mu=(1+o(1))t^{2}q^{1-n}$). The assertion follows. ∎

Proposition 5.3 implies the following.

######  Corollary 5.4.

For $n\geq 4$, let ${\mathcal{C}}$ be a cap of size $t$ in $\mathrm{PG}(n,q)$.
If $|h-h_{p}|$ is bounded by a constant, then
$t=O(q^{\frac{5}{6}n-\frac{1}{6}})$. The above holds for $q\rightarrow\infty$
as well as $n\rightarrow\infty$.

For $q=3$, Edel constructed caps of size $\Omega(2.21^{n})$ [10] and there is
an upper bound of $o(2.76^{n})$ by Ellenberg and Gijswijt [12]. For the
special cases of Corollary 5.4, we find upper bounds of $o(2.50^{n})$ for (i).
In general it is known that $t\leq(1-O(q^{-\frac{1}{2}}))q^{n-1}$ (as
$q\rightarrow\infty$), cf. Table 4.4(ii) in [14].

###  5.2 Optimally Pseudorandom Clique-free Graphs

A $k$-regular graph $\Gamma$ of order $v$ is called optimally pseudorandom if
the second largest eigenvalue in absolute value of its adjacency matrix is in
$O(\sqrt{k})$, cf. [15].

######  Proposition 5.5 (Alon and Krivelevich, [3]).

Let $\Gamma$ be a $K_{m}$-free $k$-regular graph of order $v$ with smallest
eigenvalue $s$ such that $-s=O(\sqrt{k})$. Then

$k=O(v^{1-\frac{1}{2m-3}}).$

This bound is tight for $m=3$ due to a construction by Alon [2]. Alon and
Krivelevich gave an example with $k=\Theta(v^{1-\genfrac{}{}{}{3}{1}{m-2}})$
[3]. The author noticed that there is a well-known construction with
$k=\Theta(v^{1-\genfrac{}{}{}{3}{1}{m-1}})$ [4]. These are the graphs
$NO^{\varepsilon\perp}_{m,q}$ from §4 with clique number $m-1$.

The Ramsey number $R(m,n)$ is the largest number such that there exists a
graph on $R(m,n)-1$ vertices without a clique of size $m$ or an independent
set of size $n$. Ajtai, Komlós, and Szemerédi [1] and Bohman and Keevash [5]
proved

$\displaystyle\Omega\left(\tfrac{n^{\frac{m+1}{2}}}{(\log
n)^{\genfrac{}{}{}{3}{m+1}{2}-\genfrac{}{}{}{3}{1}{m-2}}}\right)=R(m,n)=O\left(\tfrac{n^{m-1}}{(\log
n)^{m-2}}\right)$ $\displaystyle\text{(as $n\rightarrow\infty$)}.$

Recently, Mubayi and Verstraëte showed in [16] that if the upper bound in
Proposition 5.5 is tight for some $m$, then
$R(m,n)=\Omega(\frac{n^{m-1}}{(\log n)^{2m-4}})$, nearly matching the upper
bound. Their result also implies that if one finds a construction with
$k=\Omega(v^{1-\genfrac{}{}{}{3}{1}{m+\varepsilon}})$ for some
$\varepsilon>0$, then

$\displaystyle R(m,n)=\Omega\left(\tfrac{n^{\frac{m+\varepsilon+1}{2}}}{(\log
n)^{m+\varepsilon+1}}\right)$ $\displaystyle\text{(as $n\rightarrow\infty$)},$

which would improve the lower bound on $R(n,m)$. Our technique here cannot
show anything better than $k=O(v^{1-\genfrac{}{}{}{3}{1}{m+1}})$.

For the remainder of the section consider an optimally pseudorandom
$K_{m}$-free $k$-regular graph $\Gamma$ of order $v$, smallest eigenvalue $s$,
and second largest eigenvalue $r$, where $m\geq 3$. Let $Y$ be a clique of
size $i$ of $\Gamma$. Let $\Gamma(Y)$ be the induced subgraph on the common
neighborhood of $Y$. Let us define the following properties for
$\Gamma_{i}\coloneq\Gamma(Y)$.

  1. (P1)

The graph $\Gamma_{i}$ has $v_{i}$ vertices and $\frac{1}{2}v_{i}k_{i}$ edges,
where

$\displaystyle k_{i}\geq(1+o(1))k\left(\tfrac{k}{v}\right)^{i},$
$\displaystyle(1+o(1))\tfrac{k}{v}\leq\tfrac{k_{i}}{v_{i}}=o(1).$

  2. (P2)

The graph $\Gamma_{i}$ is approximately strongly regular with parameters
$(v_{i},k_{i},\lambda_{i},\allowbreak\mu_{i};\sigma_{i})$ and its smallest
eigenvalue $s_{i}$ satisfies

$-s_{i}=O(\mu_{i}-\lambda_{i}).$

Clearly, the graphs $NO^{\varepsilon\perp}_{m,q}$ with clique number $m-1$
satisfy (P1). Furthermore, as mentioned in §4, the automorphism group of
$NO^{\varepsilon\perp}_{m,q}$ acts transitively on cliques of a given size.
Hence, $\Gamma_{i}$ is regular. The graphs $NO^{\varepsilon\perp}_{m,q}$ with
clique number $m-1$ often have property (P2). We will see that property (P2)
follows from (P1) for $i=m-3$ when $\Gamma_{m-3}$ is regular as $\Gamma_{m-3}$
is triangle-free, so $\lambda_{m-3}=0$. More generally, some $\Gamma_{i}$ must
have property (P2) as
$\lambda_{i}\leq(D+o(1))\genfrac{}{}{}{3}{k_{i}^{2}}{v_{i}}$ has to occur for
some $D<1$ for some $i$.

Let us state the expander-mixing lemma for the special case of only one set,
see the proof of Proposition 1.1.6 in [7].

######  Lemma 5.6 (Expander-Mixing Lemma, Variant).

Let $Y$ be a set of vertices of size $y$ of a $k$-regular graph $\Gamma$ of
order $v$ with second largest eigenvalue $r$ and smallest eigenvalue $s$. Then
the number $e$ of edges in the induced subgraph on $Y$ satisfies

$\tfrac{1}{2}y\left(\tfrac{y(k-s)}{v}+s\right)\leq
e\leq\tfrac{1}{2}y\left(\tfrac{y(k-r)}{v}+r\right).$

######  Lemma 5.7.

Let $0\leq i\leq m-3$.

  1. (i)

If $k=\omega(v^{1-\frac{1}{2i{+}1}})$, then there exists a $\Gamma_{i}$ with
property (P1).

  2. (ii)

If $\Gamma_{i}$ is regular and has property (P1), then

$-s_{i}=\Omega\left(k_{i}\left(\tfrac{k_{i}}{v_{i}}\right)^{m-i-2}\right).$

###### Proof.

First we show (i). For this, let $k_{i}$ denote the average degree of
$\Gamma_{i}$. Clearly, the claim is true for $i=0$. The condition
$k=\omega(v^{1-\frac{1}{2i{+}1}})$ is equivalent to

$\displaystyle(1+o(1))k\left(\tfrac{k}{v}\right)^{i}=\omega(\sqrt{k}).$ (1)

Suppose that the claim is true for $\Gamma_{i-1}=\Gamma(Y)$ for some clique
$Y$ of size $i-1$. Let $a$ be a vertex of $\Gamma_{i-1}$ of degree at least
$k_{i-1}$. Take $\Gamma_{i}=\Gamma(Y\cup\\{a\\})$. By Lemma 5.6 applied to
$\Gamma$, using Equation (1), the average degree $k_{i}$ of a vertex in
$\Gamma_{i}$ satisfies

$\displaystyle(1+o(1))k\left(\tfrac{k}{v}\right)^{i}\leq\tfrac{k_{i-1}(k-s)}{v}+s\leq
k_{i}\leq\tfrac{k_{i-1}(k-r)}{v}+r=(1+o(1))k_{i-1}\cdot\tfrac{k}{v}.$

This shows property (P1) for $\Gamma_{i}$.

Next we show (ii). For some $j$ with $i\leq j\leq m-3$ we require that
$\lambda_{j}<(D+o(1))\frac{k_{j}^{2}}{v_{j}}$ for some constant $D<1$ as
$\Gamma$ is $K_{m}$-free. Similarly to the above, for the first $j$ for which
this occurs, we find a $\Gamma_{j}$ with

$k_{j}=(1+o(1))k_{i}\left(\tfrac{k_{i}}{v_{i}}\right)^{j-i}.$

By Lemma 5.6, applied to the regular graph $\Gamma_{i}$,

$(D+o(1))\tfrac{k_{j}^{2}}{v_{j}}\geq\lambda_{j}\geq(1+o(1))k_{i}\left(\tfrac{k_{i}}{v_{i}}\right)^{j-i+1}+s_{i}.$

In the worst case is $j=m-3$ which yields the claim. ∎

######  Proposition 5.8.

Suppose that $\Gamma$ has $k=\allowbreak\omega(v^{1-\frac{1}{3m{-}2i{-}5}})$.
Furthermore, suppose that $\Gamma_{i}$ has property (P1), and that
$\Gamma_{i}$ has property (P2) or $i=m-3$. If $\Gamma_{i}$ is regular, then
$\sigma_{i}=\Omega(\sqrt{k}\left(\tfrac{k}{v}\right)^{\frac{3}{2}m-2-i})$.

###### Proof.

If $\Gamma_{i}$ has property (P1) and is regular, then it is an approximately
strongly regular graph with parameters
$(v_{i},k_{i},\lambda_{i},\mu_{i};\sigma_{i})$ with
$\mu_{i}=(1+o(1))\frac{k_{i}^{2}}{v_{i}^{2}}$ (as $k_{i}=o(v)$). If
$\Gamma_{m-3}$ has property (P1), then $\lambda_{m-3}=0$ and
$\mu_{m-3}=(1+o(1))\frac{k_{m-3}^{2}}{v_{m-3}}$, so $\Gamma_{m-3}$ has
property (P2).

By Lemma 5.7(ii) and property (P2),

$\mu_{i}-\lambda_{i}=\Omega\left(k_{i}\left(\tfrac{k}{v}\right)^{m-i-2}\right).$

From $k=\omega(v^{1-\frac{1}{3m{-}2i{-}5}})$ and
$k_{i}\geq(1+o(1))k\left(\frac{k}{v}\right)^{i}$, we obtain that
$k_{i}=o(|\mu_{i}-\lambda_{i}|^{\frac{3}{2}})$. By Proposition 3.4,

$\displaystyle\sigma_{i}$
$\displaystyle\geq(1+o(1))\frac{|\mu-\lambda|}{v}=\Omega\left(\sqrt{k}\left(\tfrac{k}{v}\right)^{\frac{3}{2}m-2-i}\right).\qed$

For $i\leq\frac{3}{4}m-\frac{3}{2}$, we have
$k=\omega(v^{1-\frac{1}{2i{+}1}})$ in Proposition 5.8, so we can apply Lemma
5.7(i) and see that there exists a $\Gamma_{i}$ with property (P1). Hence, the
case $i=\lfloor\frac{3}{4}m-\frac{3}{2}\rfloor$ is special.

######  Corollary 5.9.

Let $m\geq 5$. Let $\Gamma_{i}$ be as in Proposition 5.8.

  1. (i)

If $i=\frac{3}{4}m-\frac{3}{2}$, and
$\sigma_{i}=o(\sqrt{k}\left(\tfrac{k}{v}\right)^{\frac{3}{4}m-\frac{1}{2}})$,
then $k=O(v^{1-\frac{2}{3m-4}})$.

  2. (ii)

If $i=m-3$ and
$\sigma_{m-3}=o(\sqrt{k}\left(\tfrac{k}{v}\right)^{\frac{1}{2}m+1})$, then
$k=O(v^{1-\frac{1}{m+1}})$.

##  6 Future Work

There are countless results specific to strongly regular graphs. Generalizing
them to approximately strongly regular graphs seems to be a worthwhile
endeavor. Maybe one can improve the bounds given here: our variant of the
absolute bound, Proposition 3.5, is not very satisfying compared to our Krein
bounds. An earlier version of this document contained a much better version of
Proposition 3.5 under the assumption that the graph is also $1$-walk-regular
(cf. [8]). While our proof was incorrect, we believe that much stronger
versions of Proposition 3.5 should hold for slightly stronger regularity
conditions. There is also the question if our results – using the usual
connections between caps, strongly regular graphs, and linear codes – has any
interesting implications for coding theory.

Our primary motivation for this document is to restrict the search space when
looking for constructions for specific extremal problems. Maybe the techniques
in this paper can be expanded to obtain more general bounds on caps and
optimally pseudorandom clique-free graphs. At the time of writing, the author
holds the weak belief that Corollary 5.4 and Corollary 5.9 state true upper
bounds for the respective general cases.

#### Acknowledgment

The author is supported by a postdoctoral fellowship of the Research
Foundation – Flanders (FWO).

The author thanks Andries E. Brouwer for several suggestions, particularly,
for the term approximately strongly regular graphs, Dion Gijswijt for several
comments on an earlier version of this manuscript, and Jacques Verstraëte for
hosting him for the last two months in 2021 and discussing caps and clique-
free graphs.222 The author knows for neither of them if they approve of the
present version of this document. Thus, if you disagree with this text, solely
its author is to blame.

## References

  * [1] M. Ajtai, J. Komlós, and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29(3) (1980) 354–360.
  * [2] N. Alon, Explicit Ramsey graphs and orthonormal labelings, Electronic J. Combin. 1 (1994) #R12.
  * [3] N. Alon and M. Krivelevich, Constructive Bounds for a Ramsey-Type Problem, Graphs Combin. 13(3) (1997) 217–225.
  * [4] A. Bishnoi, F. Ihringer, and V. Pepe, A construction of clique-free pseudorandom graphs, Combinatorica 40(3) (2020) 307–314.
  * [5] T. Bohman and P. Keevash, The early evolution of the H-free process, Invent. Math. 181 (2010) 291–336.
  * [6] A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Springer, Heidelberg, 1989.
  * [7] A. E. Brouwer and H. Van Maldeghem, Strongly Regular Graphs, Cambridge University Press, Encyclopedia of Mathematics and Its Applications 182, 2022.
  * [8] C. Dalfó, M.A. Fiol, and E. Garriga, On $k$-Walk-Regular Graphs, Electronic J. Combin. 16 (2009) #R47.
  * [9] Ph. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geom. Dedicata 6 (1977) 363–388.
  * [10] Y. Edel, Extensions of generalized product caps, Des. Codes Cryptogr. 31(1) (2004) 5–14.
  * [11] Y. Edel, J. Bierbrauer, Recursive constructions for large caps, Bull. Belg. Math. Soc. 6 (1999) 249–258.
  * [12] J. S. Ellenberg and D. Gijswijt, On large subsets of ${\mathbb{F}}_{q}^{n}$ with no three-term progression, Ann. of Math. 185 (2017) 339–343.
  * [13] W. H. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 226–228 (1995) 593–616.
  * [14] W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: Update 2001, in Finite Geometries, A. Blokhuis, J. W. P. Hirschfeld, D. Jungnickel, and J. A. Thas, eds., Kluwer, Dodrecht, 2001, 201–246.
  * [15] M. Krivelevich and B. Sudakov, Pseudo-random graphs, in: Bolyai Soc. Math. Stud., vol. 15, Springer, Berlin, 199–262, 2006.
  * [16] D. Mubayi and J. Verstraëte, A note on pseudorandom Ramsey graphs, arXiv:1909.01461 (2019).
  * [17] D. E. Taylor, The Geometry of the Classical Groups, Heldermann, Berlin, 1992.