Increasingly many bounded eigenvalues of the graph of Whitehead moves

Michael Li

May 23, 2024

###### Abstract

In this paper, we investigate the eigenvalues of the Laplacian matrix of the
“graph of graphs”, in which cubic graphs of order $n$ are joined together
using Whitehead moves. Our work follows recent results from [dPK23], which
discovered a significant “bottleneck” in the graph of graphs. We found that
their bottleneck implies an eigenvalue of order at most $O(1)$. In fact, our
main contribution is to expand upon this result by showing that the graph of
graphs has increasingly many bounded eigenvalues as $n\to\infty$. We also show
that these eigenvalues are unusually small, in the sense that they are much
smaller than the eigenvalues of a random regular graph with an equal number of
vertices and a similar degree.

##  1 Introduction

A cubic graph is defined to be a connected graph, possibly with loops and
multiple edges, such that the degree of each vertex is $3$ (a loop counts
twice). The vertices may be labelled or unlabelled. In a cubic graph, given
any edge $e$ that is not a loop, a Whitehead move on $e$ is a move where two
edges incident to the endpoints of $e$ are swapped. If the cubic graph is
unlabelled, then there are 2 possible Whitehead moves on $e$, as illustrated
below:

$e$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$e$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$e$$v_{1}$$v_{2}$$v_{3}$$v_{4}$

Figure 1.1: The definition of a Whitehead move.

If the cubic graph is labelled, then there are 4 different Whitehead moves
instead, since each endpoint of $e$ has $2$ distinct choices of which edge to
swap to the other endpoint.

Next, we will define the “graph of graphs”. For all even $n\in\mathbb{N}$, let
$\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$ be the simple graphs whose vertices are
all $n$-vertex labelled and unlabelled cubic graphs, respectively. In both
$\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$, let two distinct cubic graphs be joined
by an edge if they can be transformed into each other with a Whitehead move.
Note that Whitehead moves are reversible, so all edges in $\Gamma^{l}_{n}$ and
$\Gamma^{u}_{n}$ are undirected. It is also known that $\Gamma^{l}_{n}$ and
$\Gamma^{u}_{n}$ are both connected (e.g., [RT13]).

Now, for any graph $G$, we define its Laplacian matrix as follows. First, let
the directed incidence matrix $C(G)$ be the matrix whose columns correspond to
vertices and whose rows correspond to edges, such that for each edge, we place
a $-1$ at one endpoint and a $+1$ at the other endpoint. Then, we define the
Laplacian matrix to be $Q(G)\mathrel{\mathop{\ordinarycolon}}=C(G)^{T}\cdot
C(G)$. As an alternative formula, we also have $Q(G)=D(G)-A(G)$, where $D(G)$
denotes the diagonal matrix with entries equal to the degrees of the vertices
of $G$, and $A(G)$ denotes the adjacency matrix. Note that $Q(G)$ is
symmetric, so its eigenvalues are real, and it has an orthonormal basis of
eigenvectors. Then, let
$\lambda_{1}(G)\leq\lambda_{2}(G)\leq\cdots\leq\lambda_{N}(G)$ be its
eigenvalues (with multiplicity), and let $(v_{1}(G),v_{2}(G),\dots,v_{N}(G))$
be a corresponding orthonormal basis of eigenvectors. It is known (e.g.,
[AM85]) that $\lambda_{1}(G)=0$ with the constant eigenvector, and that
$\lambda_{2}(G)>0$ if $G$ is connected. In particular, all eigenvalues of
$\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$ except for $\lambda_{1}$ are positive.

For all connected $G$, we will also define a related quantity called its
conductance (sometimes also called the edge isoperimetric number or the
Cheeger constant). First, for any proper subset $X\subset V(G)$, we define its
boundary $\partial X$ to be the set of edges between $X$ and $V(G)-X$, and we
also define its conductance to be:

$\phi(X)\mathrel{\mathop{\ordinarycolon}}=\frac{\,\mathinner{\\!\left\lvert\partial
X\right\rvert}}{\min(\,\mathinner{\\!\left\lvert
X\right\rvert},\,\mathinner{\\!\left\lvert V(G)-X\right\rvert})}.$

Then, we define the conductance of the entire graph $G$ to be:

$\phi(G)\mathrel{\mathop{\ordinarycolon}}=\min_{X\subset V(G)}\phi(X).$

Finally, we will use a “bottleneck” in $G$ as a heuristic term for a subset
$X\subset V(G)$ such that $\phi(X)$ is small (usually $O(1)$ or smaller if $G$
is an infinite family of graphs).

The goal of this paper is to answer McMullen’s question of whether or not
$\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$ are expander families (as described in
[Raf23]). One version of this question asks how small the smallest positive
eigenvalues of $\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$ are. So far, here is our
best result:

Theorem 1.1: For all $k\in\mathbb{N}$, there exist constants $c^{l}_{k}$ and
$c^{u}_{k}$ such that for all sufficiently large $n$, the
$k^{\text{th}}$-smallest eigenvalues of $\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$
satisfy $\lambda_{k}(\Gamma^{l}_{n})\leq c^{l}_{k}$ and
$\lambda_{k}(\Gamma^{u}_{n})\leq c^{u}_{k}$.

In contrast, for a typical graph with similar parameters, which we will
represent using a random regular graph, one would expect its smallest positive
eigenvalues to increase without bound as the graph’s degree increases. For
instance, [BS87] showed results which imply that the smallest positive
eigenvalue of a random $d$-regular graph is approximately $d$. Thus, the
eigenvalues of $\Gamma^{l}_{n}$ are also unusually small, as expressed in the
following theorem (which we will make more precise in Section 4):

Theorem 1.2: As $n$ increases to infinity, $\Gamma^{l}_{n}$ has increasingly
many eigenvalues smaller than the smallest positive eigenvalue of a comparable
random regular graph.

To prove these theorems, we begin in Section 2 by reviewing several useful
relations between the eigenvalues of a connected graph $G$ and the conductance
of bottlenecks in $G$. Then, in Section 3, we will prove Theorem 1.1 by
finding a series of independent bottlenecks in $\Gamma^{l}_{n}$ and
$\Gamma^{u}_{n}$ by expanding upon results in [dPK23]. The main insight behind
our series of bottlenecks is that if a cubic graph has a specific local
structure or feature (such as a cycle of some fixed length), then only
Whitehead moves contained in or incident to the local structure can change it,
so there are very few corresponding edges in $\Gamma^{l}_{n}$ or
$\Gamma^{u}_{n}$ that connect to graphs without the local structure. Next, in
Section 4, we will explain why it is appropriate to compare $\Gamma^{l}_{n}$
to a random regular graph, then we will prove Theorem 1.2. Finally, in Section
5, we will discuss some conjectures and open questions from our research.

##  2 Relations between eigenvalues and conductance

To begin, for any symmetric matrix $M$ and any nonzero vector $v$ of the same
size, the Rayleigh quotient of $v$ is defined to be:

$J(M,v)\mathrel{\mathop{\ordinarycolon}}=\frac{\langle
Mv,v\rangle}{\mathinner{\\!\left\lVert
v\right\rVert}^{2}}=\frac{v^{T}Mv}{\mathinner{\\!\left\lVert
v\right\rVert}^{2}}.$

In particular, given a connected graph $G$ and a nonzero vector
$f\mathrel{\mathop{\ordinarycolon}}V(G)\to\mathbb{R}$, the Rayleigh quotient
of $f$ equals:

$J(G,f)\mathrel{\mathop{\ordinarycolon}}=J(Q(G),f)=\frac{f^{T}Q(G)f}{\sum
f(v)^{2}}=\frac{f^{T}C(G)^{T}C(G)f}{\sum
f(v)^{2}}=\frac{\mathinner{\\!\left\lVert C(G)f\right\rVert}^{2}}{\sum
f(v)^{2}}=\frac{\sum_{uv\in E(G)}(f(u)-f(v))^{2}}{\sum f(v)^{2}}.$

Then, the well-known Rayleigh principle states that:

$\lambda_{2}(G)=\min_{\sum f=0}J(G,f).$

This fact is useful for estimating $\lambda_{2}(G)$ if we find a vector $f$
with a sufficiently low Rayleigh quotient. In particular, a bottleneck in $G$
implies a low value for $\lambda_{2}(G)$, as expressed in Cheeger’s
Inequality:

Proposition 2.1 (Cheeger’s Inequality): For every proper subset $X\subset
V(G)$, we have $\lambda_{2}(G)\leq 2\phi(X)$. (Similar results for the vertex
isoperimetric number were previously proven by [Alo86].)

Proof: In fact, we will introduce a bottleneck vector corresponding to $X$
with a Rayleigh quatient of at most $2\phi(X)$. Given any proper subset
$X\subset V(G)$, if we denote $Y\mathrel{\mathop{\ordinarycolon}}=V(G)-X$,
then let us define the bottleneck vector of $X$ to be the vector
$f\mathrel{\mathop{\ordinarycolon}}V(G)\to\mathbb{R}$ such that:

$f(v)=\begin{cases}-\frac{\,\mathinner{\\!\left\lvert
Y\right\rvert}}{\sqrt{\,\mathinner{\\!\left\lvert
X\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y\right\rvert}\cdot\,\mathinner{\\!\left\lvert V(G)\right\rvert}}},&\text{ if
}v\in X;\\\ \frac{\,\mathinner{\\!\left\lvert
X\right\rvert}}{\sqrt{\,\mathinner{\\!\left\lvert
X\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y\right\rvert}\cdot\,\mathinner{\\!\left\lvert V(G)\right\rvert}}},&\text{ if
}v\in Y.\end{cases}$

Then, $\sum f=0$ and $\mathinner{\\!\left\lVert f\right\rVert}^{2}=\sum
f^{2}=1$. Also, this bottleneck vector has a Rayleigh quotient of:

$\displaystyle J(G,f)$ $\displaystyle=\frac{1}{\sum f(v)^{2}}\cdot\sum_{uv\in
E(G)}(f(u)-f(v))^{2}$ $\displaystyle=1\cdot\,\mathinner{\\!\left\lvert\partial
X\right\rvert}\cdot\frac{(\,\mathinner{\\!\left\lvert
X\right\rvert}+\,\mathinner{\\!\left\lvert
Y\right\rvert})^{2}}{\,\mathinner{\\!\left\lvert
X\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y\right\rvert}\cdot(\,\mathinner{\\!\left\lvert
X\right\rvert}+\,\mathinner{\\!\left\lvert Y\right\rvert})}$
$\displaystyle=\frac{\,\mathinner{\\!\left\lvert\partial
X\right\rvert}\cdot(\,\mathinner{\\!\left\lvert
X\right\rvert}+\,\mathinner{\\!\left\lvert
Y\right\rvert})}{\,\mathinner{\\!\left\lvert
X\right\rvert}\cdot\,\mathinner{\\!\left\lvert Y\right\rvert}}$
$\displaystyle\leq\frac{\,\mathinner{\\!\left\lvert\partial
X\right\rvert}\cdot 2\max(\,\mathinner{\\!\left\lvert
X\right\rvert},\,\mathinner{\\!\left\lvert
Y\right\rvert})}{\,\mathinner{\\!\left\lvert
X\right\rvert}\cdot\,\mathinner{\\!\left\lvert Y\right\rvert}}$
$\displaystyle=\frac{2\,\mathinner{\\!\left\lvert\partial
X\right\rvert}}{\min(\,\mathinner{\\!\left\lvert
X\right\rvert},\,\mathinner{\\!\left\lvert Y\right\rvert})}$
$\displaystyle=2\phi(X).$

From the Rayleigh principle, we conclude that $\lambda_{2}(G)\leq J(G,f)\leq
2\phi(X)$, as required. ∎

Next, we wish to develop more powerful tools to extract more small eigenvalues
from a graph with multiple bottlenecks, as long as the bottlenecks are
“different enough”. Hence, borrowing from the statistical notion of
independence, let us define two bottlenecks $X_{1},X_{2}\subset V(G)$ to be
independent if:

$\frac{\,\mathinner{\\!\left\lvert X_{1}\cap
X_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}=\frac{\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert V(G)\right\rvert}}.$

Unfortunately, independent bottlenecks is an ideal that we cannot always
achieve, so let us define the covariance of two bottlenecks
$X_{1},X_{2}\subset V(G)$ to be:

$\operatorname{Cov}(X_{1},X_{2})\mathrel{\mathop{\ordinarycolon}}=\frac{\,\mathinner{\\!\left\lvert
X_{1}\cap X_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}-\frac{\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert V(G)\right\rvert}}.$

Then, two nearly independent bottlenecks will have nearly orthogonal
bottleneck vectors, as expressed in the following lemma:

Lemma 2.2: Given $X_{1},X_{2}\subset V(G)$, their bottleneck vectors
$f_{1},f_{2}$ have an inner product of:

$\langle
f_{1},f_{2}\rangle=\operatorname{Cov}(X_{1},X_{2})\cdot\sqrt{\frac{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}{\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)-X_{1}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}{\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}{\,\mathinner{\\!\left\lvert V(G)-X_{2}\right\rvert}}}.$

Proof: Let us denote $Y_{1}\mathrel{\mathop{\ordinarycolon}}=V(G)-X_{1}$ and
$Y_{2}\mathrel{\mathop{\ordinarycolon}}=V(G)-X_{2}$. Then, we have:

$\displaystyle\operatorname{Cov}(X_{1},X_{2})$
$\displaystyle=\frac{\,\mathinner{\\!\left\lvert X_{1}\cap
X_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}-\frac{\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}=-\bigg{(}\frac{\,\mathinner{\\!\left\lvert X_{1}\cap
Y_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}-\frac{\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert V(G)\right\rvert}}\bigg{)}$
$\displaystyle=-\bigg{(}\frac{\,\mathinner{\\!\left\lvert Y_{1}\cap
X_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}-\frac{\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\bigg{)}=\frac{\,\mathinner{\\!\left\lvert Y_{1}\cap
Y_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}-\frac{\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}}{\,\mathinner{\\!\left\lvert V(G)\right\rvert}}.$

As a result:

$\displaystyle\text{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}
$=$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\sqrt{\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
V(G)\right\rvert}\cdot\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\cdot\langle f_{1},f_{2}\rangle$ $\displaystyle\hskip
28.45274pt=\langle\sqrt{\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert V(G)\right\rvert}}\cdot
f_{1},\sqrt{\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}\cdot\,\mathinner{\\!\left\lvert V(G)\right\rvert}}\cdot
f_{2}\rangle$ $\displaystyle\hskip 28.45274pt=\,\mathinner{\\!\left\lvert
X_{1}\cap X_{2}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}-\,\mathinner{\\!\left\lvert X_{1}\cap
Y_{2}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}-\,\mathinner{\\!\left\lvert Y_{1}\cap
X_{2}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}+\,\mathinner{\\!\left\lvert Y_{1}\cap
Y_{2}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert X_{2}\right\rvert}$
$\displaystyle\hskip
28.45274pt=\operatorname{Cov}(X_{1},X_{2})\cdot\,\mathinner{\\!\left\lvert
V(G)\right\rvert}\cdot(\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}+\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}+\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}+\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\cdot\,\mathinner{\\!\left\lvert Y_{2}\right\rvert})$
$\displaystyle\hskip
28.45274pt\text{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}
$=$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}+\frac{1}{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}\cdot(\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}-\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}-\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}+\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}\,\mathinner{\\!\left\lvert
Y_{2}\right\rvert}\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}\,\mathinner{\\!\left\lvert X_{2}\right\rvert})$
$\displaystyle\hskip
28.45274pt=\operatorname{Cov}(X_{1},X_{2})\cdot\,\mathinner{\\!\left\lvert
V(G)\right\rvert}\cdot(\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}+\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert})\cdot(\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}+\,\mathinner{\\!\left\lvert Y_{2}\right\rvert})+0$
$\displaystyle\hskip
28.45274pt=\operatorname{Cov}(X_{1},X_{2})\cdot\,\mathinner{\\!\left\lvert
V(G)\right\rvert}^{3}.$

We conclude that:

$\langle
f_{1},f_{2}\rangle=\operatorname{Cov}(X_{1},X_{2})\cdot\sqrt{\frac{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}{\,\mathinner{\\!\left\lvert
X_{1}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}{\,\mathinner{\\!\left\lvert
Y_{1}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}{\,\mathinner{\\!\left\lvert
X_{2}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(G)\right\rvert}}{\,\mathinner{\\!\left\lvert Y_{2}\right\rvert}}}\,,$

as required. ∎

If $G$ has multiple nearly independent bottlenecks, it follows from Lemma 2.2
that $G$ has multiple bottleneck vectors with low Rayleigh quotients such that
they are nearly orthogonal to each other and to the constant eigenvector. The
next linear algebra theorem helps us to conclude that $G$ has multiple small
eigenvalues:

Theorem 2.3: Given $k$ and sufficiently small $\epsilon\geq 0$, if a symmetric
matrix $M$ with nonnegative eigenvalues has $k$ vectors $w_{1},\dots,w_{k}$
with Rayleigh quotients of at most $\Lambda$, and if
$\,\mathinner{\\!\left\lvert\langle
w_{i},w_{j}\rangle\right\rvert}\leq\epsilon\,\mathinner{\\!\left\lVert
w_{i}\right\rVert}\,\mathinner{\\!\left\lVert w_{j}\right\rVert}$ for all
$i\neq j$ (i.e., the vectors are nearly orthogonal), then $M$ has $k$
eigenvalues (including multiplicity) of size at most
$\frac{k\Lambda}{1-(k-1)\epsilon}$.

Proof: Let $\lambda_{1}\leq\cdots\leq\lambda_{n}$ be the eigenvalues of $M$ in
non-decreasing order, and let $(v_{1},\dots,v_{n})$ be a corresponding
orthonormal basis of eigenvectors. For all $1\leq i\leq k$, let the
coordinates of $w_{i}$ be $w_{i}=c_{i1}v_{1}+\cdots+c_{in}v_{n}$. By scaling,
we may assume without loss of generality that each $w_{i}$ has a norm of
$\sqrt{\frac{k}{(k-1)(1+\epsilon)}}$, so $\mathinner{\\!\left\lVert
w_{i}\right\rVert}^{2}=c_{i1}^{2}+\cdots+c_{in}^{2}=\frac{k}{(k-1)(1+\epsilon)}$.

Next, assume for contradiction that
$\lambda_{k}>\frac{k\Lambda}{1-(k-1)\epsilon}$. Then, for all $1\leq i\leq k$,
we obtain:

$\displaystyle\Lambda$ $\displaystyle\geq\frac{\langle
Mw_{i},w_{i}\rangle}{\mathinner{\\!\left\lVert w_{i}\right\rVert}^{2}}$
(Rayleigh quotient of $w_{i}$) $\displaystyle\Lambda$
$\displaystyle\geq\frac{\langle
M(c_{i1}v_{1}+\cdots+c_{in}v_{n}),c_{i1}v_{1}+\cdots+c_{in}v_{n}\rangle}{\frac{k}{(k-1)(1+\epsilon)}}$
$\displaystyle\Lambda$
$\displaystyle\geq\frac{(k-1)(1+\epsilon)}{k}\cdot\langle
c_{i1}\lambda_{1}v_{1}+\cdots+c_{in}\lambda_{n}v_{n},c_{i1}v_{1}+\cdots+c_{in}v_{n}\rangle$
$\displaystyle\Lambda$
$\displaystyle\geq\frac{(k-1)(1+\epsilon)}{k}\cdot(c_{i1}^{2}\lambda_{1}+\cdots+c_{in}^{2}\lambda_{n})$
$\displaystyle\Lambda$
$\displaystyle\geq\frac{(k-1)(1+\epsilon)}{k}\cdot(c_{ik}^{2}\lambda_{k}+c_{i(k+1)}^{2}\lambda_{k+1}+\cdots+c_{in}^{2}\lambda_{n})$
(Since $\lambda_{1},\dots,\lambda_{k-1}\geq 0$) $\displaystyle\Lambda$
$\displaystyle\geq\frac{(k-1)(1+\epsilon)}{k}\cdot(c_{ik}^{2}+\cdots+c_{in}^{2})\lambda_{k}\,,$
(Since $\lambda_{k}\leq\lambda_{k+1}\leq\cdots\leq\lambda_{n}$)

which gives us:

$\displaystyle\frac{1}{(k-1)(1+\epsilon)}\cdot\frac{k\Lambda}{\lambda_{k}}$
$\displaystyle\geq c_{ik}^{2}+\cdots+c_{in}^{2}$
$\displaystyle\frac{1-(k-1)\epsilon}{(k-1)(1+\epsilon)}$
$\displaystyle>c_{ik}^{2}+\cdots+c_{in}^{2}.$ (Since we assumed
$\lambda_{k}>\frac{k\Lambda}{1-(k-1)\epsilon}$)

Next, for all $1\leq i\leq k$, let us define
$a_{i}\mathrel{\mathop{\ordinarycolon}}=(c_{i1},\dots,c_{i(k-1)})\in\mathbb{R}^{k-1}$
and
$b_{i}\mathrel{\mathop{\ordinarycolon}}=(c_{ik},\dots,c_{in})\in\mathbb{R}^{n-k+1}$.
Then, we showed above that $\mathinner{\\!\left\lVert
b_{i}\right\rVert}^{2}<\frac{1-(k-1)\epsilon}{(k-1)(1+\epsilon)}$, which also
implies that:

$\mathinner{\\!\left\lVert a_{i}\right\rVert}^{2}=\mathinner{\\!\left\lVert
w_{i}\right\rVert}^{2}-\mathinner{\\!\left\lVert
b_{i}\right\rVert}^{2}>\frac{k}{(k-1)(1+\epsilon)}-\frac{1-(k-1)\epsilon}{(k-1)(1+\epsilon)}=1.$

Next, for all $1\leq i<j\leq k$, from our near-orthogonality hypothesis, we
obtain:

$\displaystyle\,\mathinner{\\!\left\lvert\langle
w_{i},w_{j}\rangle\right\rvert}$
$\displaystyle\leq\epsilon\,\mathinner{\\!\left\lVert
w_{i}\right\rVert}\,\mathinner{\\!\left\lVert w_{j}\right\rVert}$
$\displaystyle\,\mathinner{\\!\left\lvert\langle a_{i},a_{j}\rangle+\langle
b_{i},b_{j}\rangle\right\rvert}$
$\displaystyle\leq\frac{k\epsilon}{(k-1)(1+\epsilon)}$
$\displaystyle\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}-\,\mathinner{\\!\left\lvert\langle
b_{i},b_{j}\rangle\right\rvert}$
$\displaystyle\leq\frac{k\epsilon}{(k-1)(1+\epsilon)}$ (Triangle inequality)
$\displaystyle\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}$
$\displaystyle\leq\,\mathinner{\\!\left\lvert\langle
b_{i},b_{j}\rangle\right\rvert}+\frac{k\epsilon}{(k-1)(1+\epsilon)}$
$\displaystyle\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}$ $\displaystyle\leq\mathinner{\\!\left\lVert
b_{i}\right\rVert}\cdot\mathinner{\\!\left\lVert
b_{j}\right\rVert}+\frac{k\epsilon}{(k-1)(1+\epsilon)}$ (Cauchy-Schwarz)
$\displaystyle\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}$
$\displaystyle<\frac{1-(k-1)\epsilon}{(k-1)(1+\epsilon)}+\frac{k\epsilon}{(k-1)(1+\epsilon)}$
$\displaystyle\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}$ $\displaystyle<\frac{1}{k-1}.$

On the other hand, this contradicts the following claim:

Claim: Given any $k$ vectors $a_{1},\dots,a_{k}$ of magnitude at least $1$ in
$\mathbb{R}^{k-1}$, there exist $i\neq j$ such that
$\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}\geq\frac{1}{k-1}$.

Proof of Claim: We proceed by induction. The base case $k=2$ is trivial. For
the general case, let $k\geq 3$ be given, and assume for induction that the
Lemma is true for $k-1$. Then, we need to prove that there exists some pair
$a_{i},a_{j}$ such that $\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}\geq\frac{1}{k-1}$.

Assume for contradiction that $\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}<\frac{1}{k-1}$ for all $1\leq i<j\leq k$. For
all $1\leq i\leq k$, let the coordinates of $a_{i}$ be
$a_{i}=(x_{i1},\dots,x_{i(k-2)},y_{i})$, and let us define
$x_{i}\mathrel{\mathop{\ordinarycolon}}=(x_{i1},\dots,x_{i(k-2)})$. By
rotating the vectors, we may assume without loss of generality that
$a_{k}=(0,\dots,0,y_{k})$, where $y_{k}\geq 1$. Then, for all $1\leq i\leq
k-1$, from $\,\mathinner{\\!\left\lvert\langle
a_{i},a_{k}\rangle\right\rvert}<\frac{1}{k-1}$, we obtain
$\,\mathinner{\\!\left\lvert y_{i}\cdot y_{k}\right\rvert}<\frac{1}{k-1}$, so
$\,\mathinner{\\!\left\lvert
y_{i}\right\rvert}<\frac{1}{y_{k}(k-1)}\leq\frac{1}{k-1}$. This also gives us:

$\mathinner{\\!\left\lVert x_{i}\right\rVert}=\sqrt{\mathinner{\\!\left\lVert
a_{i}\right\rVert}^{2}-\,\mathinner{\\!\left\lvert
y_{i}\right\rvert}^{2}}>\sqrt{1-\frac{1}{(k-1)^{2}}}=\frac{\sqrt{k^{2}-2k}}{k-1}.$

Next, applying the induction hypothesis to the vectors
$\frac{k-1}{\sqrt{k^{2}-2k}}\cdot x_{i}$ for $1\leq i\leq k-2$, there exist
$1\leq i<j\leq k-2$ such that:

$\,\mathinner{\\!\left\lvert\langle
x_{i},x_{j}\rangle\right\rvert}\geq\frac{1}{k-2}\cdot\frac{k^{2}-2k}{(k-1)^{2}}=\frac{k}{(k-1)^{2}}\,,$

which implies that:

$\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}\geq\,\mathinner{\\!\left\lvert\langle
x_{i},x_{j}\rangle\right\rvert}-\,\mathinner{\\!\left\lvert
y_{i}\right\rvert}\cdot\,\mathinner{\\!\left\lvert
y_{j}\right\rvert}\geq\frac{k}{(k-1)^{2}}-\frac{1}{(k-1)^{2}}=\frac{1}{k-1}.$

This contradicts our assumption that $\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}<\frac{1}{k-1}$. Therefore, by contradiction,
there exist $i\neq j$ satisfying $\,\mathinner{\\!\left\lvert\langle
a_{i},a_{j}\rangle\right\rvert}\geq\frac{1}{k-1}$. Finally, by induction, this
Claim holds for all $k$, as required. ∎

Now, recall that after assuming for contradiction that
$\lambda_{k}>\frac{k\Lambda}{1-(k-1)\epsilon}$, we performed computations
which contradict the above Claim. Therefore, by contradiction,
$\lambda_{k}\leq\frac{k\Lambda}{1-(k-1)\epsilon}$, so $M$ has at least $k$
eigenvalues of size at most $\frac{k\Lambda}{1-(k-1)\epsilon}$. This concludes
the proof of Theorem 2.3, as required. ∎

##  3 Increasingly many bounded eigenvalues

Recall that we defined $\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$ to be the graphs
of Whitehead moves on $n$-vertex labelled and unlabelled cubic graphs,
respectively. In this section, we prove our main result: The families
$\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$ each have increasingly many bounded
eigenvalues as $n\to\infty$. We plan to do so by exhibiting a family of
increasingly many bottlenecks in $\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$, and
then applying tools from Section 2. Our solution is motivated by [dPK23],
whose bottleneck is very similar to our “$j=1$” bottleneck below.

Theorem 3.1(a): For all $j\in\mathbb{N}$, there exists a constant $a^{l}_{j}$
and a sequence of bottlenecks $(X^{l}_{j,n})_{n\geq j}$, $X^{l}_{j,n}\subset
V(\Gamma^{l}_{n})$, such that $\phi(X^{l}_{j,n})\leq a^{l}_{j}$ for all
sufficiently large $n$. Moreover, each pair of bottlenecks converges to
independence, in the sense that for all $i\neq j$, we obtain:

$\operatorname{Cov}(X^{l}_{i,n},X^{l}_{j,n})\to 0\hskip 14.22636pt\text{ as
}n\to\infty.$

Proof: Given $j\in\mathbb{N}$, let us define $X^{l}_{j,n}$ to be the subset of
$V(\Gamma^{l}_{n})$ corresponding to all cubic graphs with at least one
$j$-cycle (i.e., a cycle of length $j$). If a cubic graph has a $j$-cycle, and
if we perform a Whitehead move, then the cycle is preserved unless we perform
the Whitehead move on an edge inside the cycle or incident to the cycle. There
are at most $8j$ such moves. Thus, each vertex in $X^{l}_{j,n}$ has at most
$8j$ edges toward vertices outside $X^{l}_{j,n}$, so
$\,\mathinner{\\!\left\lvert\partial(X^{l}_{j,n})\right\rvert}\leq
8j\cdot\,\mathinner{\\!\left\lvert X^{l}_{j,n}\right\rvert}$. Additionally,
[JLR00, Thm. 9.5] implies that if we define
$\lambda_{j}\mathrel{\mathop{\ordinarycolon}}=\frac{2^{j}}{2j}$, then
$\frac{\,\mathinner{\\!\left\lvert
X^{l}_{j,n}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})\right\rvert}}\to 1-e^{-\lambda_{j}}$ as $n\to\infty$. As a
result:

$\displaystyle\phi(X^{l}_{j,n})$
$\displaystyle=\frac{\,\mathinner{\\!\left\lvert\partial_{e}(X^{l}_{j,n})\right\rvert}}{\min\Big{(}\,\mathinner{\\!\left\lvert
X^{l}_{j,n}\right\rvert},\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})-X^{l}_{j,n}\right\rvert}\Big{)}}$
$\displaystyle\leq\frac{8j\cdot\,\mathinner{\\!\left\lvert
X^{l}_{j,n}\right\rvert}}{\min\Big{(}\,\mathinner{\\!\left\lvert
X^{l}_{j,n}\right\rvert},\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})-X^{l}_{j,n}\right\rvert}\Big{)}}$
$\displaystyle=\frac{8j\cdot\frac{\,\mathinner{\\!\left\lvert
X^{l}_{j,n}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})\right\rvert}}}{\min\bigg{(}\frac{\,\mathinner{\\!\left\lvert
X^{l}_{j,n}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})\right\rvert}},1-\frac{\,\mathinner{\\!\left\lvert
X^{l}_{j,n}\right\rvert}}{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})\right\rvert}}\bigg{)}}$
$\displaystyle=\frac{8j\cdot(1-e^{-\lambda_{j}})}{\min(1-e^{-\lambda_{j}},e^{-\lambda_{j}})}+o(1).$

Since
$\frac{8j\cdot(1-e^{-\lambda_{j}})}{\min(1-e^{-\lambda_{j}},e^{-\lambda_{j}})}$
is constant, it follows that there exists a constant $a^{l}_{j}$ such that
$\phi(X^{l}_{j,n})\leq a^{l}_{j}$ for all sufficiently large $n$, as required.

Finally, [JLR00, Thm. 9.5] also implies that if we pick a random cubic graph
$G$ with $n$ vertices, then the events “$G$ has a $1$-cycle”, “$G$ has a
$2$-cycle”, etc. converge to statistically independent events as $n\to\infty$.
Therefore, the corresponding bottlenecks $X^{l}_{1,n},X^{l}_{2,n},\dots$ also
converge to independent bottlenecks, as required. ∎

With a similar argument, we also obtain the following theorem for
$\Gamma^{u}_{n}$:

Theorem 3.1(b): For all $j\in\mathbb{N}$, there exists a constant $a^{u}_{j}$
and a sequence of bottlenecks $(X^{u}_{j,n})_{n\geq j}$, $X^{u}_{j,n}\subset
V(\Gamma^{u}_{n})$, such that $\phi(X^{u}_{j,n})\leq a^{u}_{j}$ for all
sufficiently large $n$. Moreover, each pair of bottlenecks converges to
independence, in the sense that for all $i\neq j$, we obtain:

$\operatorname{Cov}(X^{u}_{i,n},X^{u}_{j,n})\to 0\hskip 14.22636pt\text{ as
}n\to\infty.$

As a remark, a similar argument can be used to find many other bottlenecks in
$\Gamma^{u}_{n}$ and $\Gamma^{l}_{n}$ by replacing “$j$-cycle” with different
local structures which also can only be changed by Whitehead moves contained
in or incident to the local structure. For example, [dPK23] found a bottleneck
by observing that a bridge, or cut-edge, in a cubic graph constitutes such a
local structure. Our bottlenecks induced by $j$-cycles will be more useful for
us because our bottlenecks are nearly independent.

Next, we can use the corresponding bottleneck vectors to prove our main
result, which states that $\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$ each have
increasingly many bounded eigenvalues as $n\to\infty$:

Theorem 1.1: For all $k\in\mathbb{N}$, there exist constants $c^{l}_{k}$ and
$c^{u}_{k}$ such that for all sufficiently large $n$, the
$k^{\text{th}}$-smallest eigenvalues of $\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$
satisfy $\lambda_{k}(\Gamma^{l}_{n})\leq c^{l}_{k}$ and
$\lambda_{k}(\Gamma^{u}_{n})\leq c^{u}_{k}$.

Proof: Again, we only present the proof for $\Gamma^{l}_{n}$; the proof for
$\Gamma^{u}_{n}$ is similar. Let any $k\in\mathbb{N}$ be given. For the
bottlenecks $X^{l}_{j,n}$ from Theorem 3.1 for $1\leq j\leq k$, let
$f^{l}_{j,n}$ be the bottleneck vector corresponding to each $X^{l}_{j,n}$.
Then, applying the proof of Proposition 2.1, $f^{l}_{j,n}$ has a Rayleigh
quotient of at most $2a^{l}_{j}$. Then, let us define
$\Lambda^{l}_{k}\mathrel{\mathop{\ordinarycolon}}=\max(2a^{l}_{1},\dots,2a^{l}_{k})$,
so that $f^{l}_{j,n}$ has a Rayleigh quotient of at most $\Lambda^{l}_{k}$ for
all $1\leq j\leq k$. Additionally, for all $1\leq i<j\leq k$, Lemma 2.2 gives
us:

$\displaystyle\langle f^{l}_{i,n},f^{l}_{j,n}\rangle$
$\displaystyle=\operatorname{Cov}(X^{l}_{i,n},X^{l}_{j,n})\cdot\sqrt{\frac{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})\right\rvert}}{\,\mathinner{\\!\left\lvert
X^{l}_{i,n}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})\right\rvert}}{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})-X^{l}_{i,n}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})\right\rvert}}{\,\mathinner{\\!\left\lvert
X^{l}_{j,n}\right\rvert}}\cdot\frac{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})\right\rvert}}{\,\mathinner{\\!\left\lvert
V(\Gamma^{l}_{n})-X^{l}_{j,n}\right\rvert}}}$
$\displaystyle=\operatorname{Cov}(X^{l}_{i,n},X^{l}_{j,n})\cdot\Bigg{(}\sqrt{\frac{1}{1-e^{-\lambda_{i}}}\cdot\frac{1}{e^{-\lambda_{i}}}\cdot\frac{1}{1-e^{-\lambda_{j}}}\cdot\frac{1}{e^{-\lambda_{j}}}}+o(1)\Bigg{)}.$

Since $\operatorname{Cov}(X^{l}_{i,n},X^{l}_{j,n})$ converges to $0$, and
since the latter term converges to a constant, it follows that $\langle
f^{l}_{i,n},f^{l}_{j,n}\rangle$ also converges to $0$ for all $1\leq i<j\leq
k$. Since we defined bottleneck vectors to be unit vectors, it follows that
$\,\mathinner{\\!\left\lvert\langle
f^{l}_{i,n},f^{l}_{j,n}\rangle\right\rvert}\leq
o(1)\,\mathinner{\\!\left\lVert
f^{l}_{i,n}\right\rVert}\,\mathinner{\\!\left\lVert f^{l}_{j,n}\right\rVert}$
for all $1\leq i<j\leq k$. Thus, by Theorem 2.3,
$\lambda_{k}(\Gamma^{l}_{n})\leq(1+o(1))k\Lambda^{l}_{k}$. We conclude that
there exists a constant $c^{l}_{k}$ such that $\lambda_{k}(\Gamma^{l}_{n})\leq
c^{l}_{k}$ for all sufficiently large $n$, as required. ∎

##  4 Comparison with random regular graphs

In Section 3, we proved that $\Gamma^{l}_{n}$ has increasingly many bounded
eigenvalues as $n\to\infty$. Now, we want to understand whether this
eigenvalue behaviour is “typical”. We will investigate this question by
comparing $\Gamma^{l}_{n}$ against an appropriate random graph with similar
parameters. In fact, it turns out that $\Gamma^{l}_{n}$ is comparable to a
regular graph of degree $6n$:

Proposition 4.1: As $n\to\infty$, the average degree of vertices in
$\Gamma^{l}_{n}$ is at least $6n-O(1)$.

Proof: First, given a labelled cubic graph $G$, let $E^{\prime}(G)\subseteq
E(G)$ be the subset of edges which are neither contained in nor incident to a
loop, multiple edge, triangle, or $4$-cycle. Then, we claim that all Whitehead
moves on edges in $E^{\prime}(G)$ produce distinct cubic graphs that are also
distinct from $G$. Indeed, let any Whitehead move $m_{1}$ on any edge
$e_{1}\in E^{\prime}(G)$ be given, and suppose that the nearby vertices are
labelled as follows:

$e_{1}$$v_{1}$$v_{2}$$u_{1}$$v_{3}$$v_{4}$$u_{2}$$e_{1}$$v_{1}$$v_{2}$$u_{1}$$v_{3}$$v_{4}$$u_{2}$

Figure 4.1: Labelling vertices affected by a Whitehead move $m_{1}$.

Note that since $e_{1}\in E^{\prime}(G)$, all 6 vertices in the diagram are
distinct. As a result, $m_{1}$ produces a graph that is distinct from $G$.
Moreover, assume for contradiction that there exists a different Whitehead
move $m_{2}$ on an edge $e_{2}\in E^{\prime}(G)$ which produces the same graph
as $m_{1}$. Then, since a Whitehead move changes at most $2$ edges, and since
the move $m_{1}$ replaces edges $u_{1}v_{2}$ and $u_{2}v_{4}$ with
$u_{1}v_{4}$ and $u_{2}v_{2}$, it follows that $m_{2}$ must replace the same
edges. As a result, $e_{2}$ must be either $u_{1}u_{2}$ or $v_{2}v_{4}$.
Moreover, since $e_{1}$ is not contained in a $4$-cycle, the edge $v_{2}v_{4}$
does not exist, so we must have $f_{2}=e_{1}$. Finally, since all 6 vertices
in the diagram are distinct, the only Whitehead move on $e_{1}$ that can
change the correct edges is $m_{1}$ itself. Therefore, no other Whitehead move
on an edge in $E^{\prime}(G)$ produces the same graph as $m_{1}$. We conclude
that all Whitehead moves on edges in $E^{\prime}(G)$ produce distinct cubic
graphs that are also distinct from $G$, as desired.

Next, let any sufficiently large $n$ be given, and let $G$ be a labelled cubic
graph corresponding to a vertex in $\Gamma^{l}_{n}$. Then, it follows from
above that all $4$ Whitehead moves on all edges in $E^{\prime}(G)$ correspond
to different edges in $\Gamma^{l}_{n}$, so the degree of the corresponding
vertex in $\Gamma^{l}_{n}$ is at least $4\,\mathinner{\\!\left\lvert
E^{\prime}(G)\right\rvert}$. Hence, it suffices to show that $E^{\prime}(G)$
is large enough. Indeed, [JLR00, Thm. 9.5] implies that the expected number of
loops, multiple edges, triangles, and $4$-cycles in a random cubic graph is
$O(1)$ as $n\to\infty$. As a result, the expected number of edges contained in
or incident to such cycles is $O(1)$, so the expected size of
$\,\mathinner{\\!\left\lvert E(G)\right\rvert}-\,\mathinner{\\!\left\lvert
E^{\prime}(G)\right\rvert}$ is $O(1)$, so the expected size of
$\,\mathinner{\\!\left\lvert E^{\prime}(G)\right\rvert}$ is
$\,\mathinner{\\!\left\lvert E(G)\right\rvert}-O(1)=\frac{3}{2}n-O(1)$.
Therefore, since the degree of the corresponding vertex in $\Gamma^{l}_{n}$ is
at least $4\,\mathinner{\\!\left\lvert E^{\prime}(G)\right\rvert}$, we
conclude that the expected degree of a vertex in $\Gamma^{l}_{n}$ is at least
$4\cdot\frac{3}{2}n-O(1)=6n-O(1)$, as required. ∎

Note that since each labelled cubic graph with $n$ vertices has $\frac{3}{2}n$
edges, and since each edge has at most $4$ available Whitehead moves, the
degree of each vertex in $\Gamma^{l}_{n}$ is at most $6n$. Thus, a
straightforward application of Markov’s inequality gives us that a high
proportion of vertices in $\Gamma^{l}_{n}$ have degree between $6n-O(1)$ and
$6n$, inclusive. As a result, we may compare $\Gamma^{l}_{n}$ against a random
regular graph with an equal number of vertices and with degree $6n-O(1)$.

Next, it is well-known that the smallest positive eigenvalue of a random
$d$-regular graph is $d-o(d)$; for instance, the results from [BS87] on the
adjacency matrix are equivalent to a random $d$-regular graph having a
smallest positive eigenvalue of $d-O(d^{\frac{3}{4}})$, with a standard
deviation of $O(\sqrt{d})$. This implies that if we set
$d_{n}\mathrel{\mathop{\ordinarycolon}}=6n-O(1)$, then the smallest positive
eigenvalue of a random regular graph with degree $d_{n}$ also increases to
infinity. In particular, since Theorem 1.1 states that the
$k^{\text{th}}$-smallest eigenvalue of $\Gamma_{n}$ is bounded above by a
constant $c_{k}$, it follows that the smallest positive eigenvalue of a random
regular graph with degree $d_{n}$ increases beyond $c_{k}$. Therefore, we
conclude the following:

Theorem 1.2: As $n$ increases to infinity, $\Gamma^{l}_{n}$ has increasingly
many eigenvalues smaller than the smallest positive eigenvalue of a comparable
random $(6n-O(1))$-regular graph. ∎

##  5 Open questions

One open question is whether or not $\Gamma^{u}_{n}$ is also comparable to a
random regular graph. The situation for $\Gamma^{u}_{n}$ is more complicated
than for $\Gamma^{l}_{n}$ because multiple different Whitehead moves on a
cubic graph can correspond to the same edge in $\Gamma^{u}_{n}$ as long as
they produce graphs which are isomorphic. This effect decreases the degrees of
vertices in $\Gamma^{u}_{n}$ by a currently unknown amount. We expect this
effect to be small because almost every cubic graph has no non-trivial
automorphisms (e.g., see [Bol82] and [MW84]). Thus, we pose the following
conjecture:

Conjecture 5.1: As $n\to\infty$, the average degree of the vertices in
$\Gamma^{u}_{n}$ is at least $3n-O(1)$.

(The main term here is $3n$ instead of $6n$ because each edge in an unlabelled
cubic graph has $2$ potential Whitehead moves instead of $4$.) In fact, our
analysis of the random graph itself in our proof of Theorem 1.2 only required
that the random graph’s degree increase to $\infty$ as $n\to\infty$. Thus, to
prove a similar theorem for $\Gamma^{u}_{n}$, it would suffice to prove the
following much weaker conjecture:

Conjecture 5.2: There exists a sequence $(d_{n})\subseteq\mathbb{N}$ such that
$d_{n}\to\infty$ as $n\to\infty$, and such that the proportion of vertices in
$\Gamma_{n}$ with degree at least $d_{n}$ converges to $1$ as $n\to\infty$.

Although this conjecture is highly plausible, it does not appear to have a
quick rigorous proof. One possible approach to prove this conjecture could be
a computationally intensive count, similarly to [MW84], to show that
isomorphisms between graphs related by Whitehead moves are very rare.

Next, we wish to know whether $\Gamma^{l}_{n}$ and $\Gamma^{u}_{n}$ have even
smaller eigenvalues and bottlenecks with even lower conductance than described
in this paper. Hence, we raise the following questions, which are related by
Proposition 2.1:

Problem 5.3: Does the smallest positive eigenvalue
$\lambda_{2}(\Gamma^{l}_{n})$ or $\lambda_{2}(\Gamma^{u}_{n})$ converge to $0$
as $n\to\infty$?

Problem 5.4: Does the conductance $\phi(\Gamma^{l}_{n})$ or
$\phi(\Gamma^{u}_{n})$ converge to $0$ as $n\to\infty$?

Finally, we also wish to understand the eigenvectors corresponding to the
small eigenvalues that we have discovered, as expressed in the following more
open-ended question:

Problem 5.5: Can we give a description of the eigenvectors corresponding to
the smallest positive eigenvalues of $\Gamma^{l}_{n}$ or $\Gamma^{u}_{n}$? For
example, can we describe how each entry $f(v)$ in an eigenvector
$f\mathrel{\mathop{\ordinarycolon}}V(\Gamma^{l}_{n})\to\mathbb{R}$ or
$f\mathrel{\mathop{\ordinarycolon}}V(\Gamma^{u}_{n})\to\mathbb{R}$ relates to
the properties of the cubic graph corresponding to $v$?

The resource [Raf23] discusses some of our early computational progress toward
this problem for $\Gamma^{u}_{n}$.

##  6 Acknowledgements

This paper is a result of a research project supervised by Kasra Rafi, funded
by the NSERC-USRA grant 516480.

The author would like to thank his professor Kasra Rafi for many fruitful and
insightful discussions (especially his suggestion to generalize the bottleneck
from [dPK23]) and for providing feedback to improve the paper, and his
colleague Summer Sun for finding several useful resources. The author would
also like to thank his family for kindly supporting him throughout the
project.

## References

  * [Alo86] N. Alon.  Eigenvalues and expanders.  Combinatorica, 6(2):83–96, 1986.
  * [AM85] W. N. Anderson Jr. and T. D. Morley.  Eigenvalues of the Laplacian of a graph.  Linear and Multilinear Algebra, 18(2):141–145, 1985.
  * [Bol82] B. Bollobás.  The asymptotic number of unlabelled regular graphs.  Journal of the London Mathematical Society (2), 26(2):201–206, 1982\.
  * [BS87] A. Broder and E. Shamir.  On the second eigenvalue of random regular graphs.  In 28th Annual Symposium on Foundations of Computer Science, pages 286–294. IEEE, 1987.
  * [dPK23] L. G. de Peralta and A. Kolpakov.  Expansion properties of Whitehead moves on cubic graphs.  arXiv preprint 2303.13923, 2023.
  * [JLR00] S. Janson, T. Luczak, and A. Rucinski.  Random graphs.  John Wiley & Sons, 2000.
  * [MW84] B. D. McKay and N. C. Wormald.  Automorphisms of random graphs with specified vertices.  Combinatorica, 4(4):325–338, 1984.
  * [Raf23] K. Rafi.  Graph of graphs.  math.toronto.edu/rafi/gofg.html, 2023.  Accessed: 2023-08-24.
  * [RT13] K. Rafi and J. Tao.  The diameter of the thick part of moduli space and simultaneous Whitehead moves.  Duke Mathematical Journal, 162(10):1833–1876, 2013.