Equiangular Lines and Eigenvalue Multiplicities

Sphere packing, spherical codes, and other geometric arrangement problems have captivated the minds of Kepler, Newton, Gauss, and countless others. Viazovska’s recent breakthrough proof of the optimality of sphere packing arrangements in dimensions 8 and 24 was recognized in her 2022 Fields Medal citation. Despite the substantial interest and effort, these problems remain poorly understood especially in high dimensions, where precise answers are exceedingly rare.

This article delves into a recent solution of a longstanding problem on optimal configurations of equiangular lines. This is a rare instance of a high-dimensional packing problem that we now understand quite precisely. As we embark on our exploration of equiangular lines, we will see a beautiful link to spectral graph theory. A surprising revelation regarding eigenvalue multiplicities emerges, and it plays a pivotal role in cracking the geometric arrangement problem.

Equiangular Lines

How many lines can there be in $\mathbb{R}^d$, all passing through the origin, and pairwise forming equal angles? In two dimensions, the answer is three.

$$\begin{equation*} \vcenter{\img[][50pt][58pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}\draw[red, thick] (90:1) -- (90:-1); \draw[red, thick] (30:1) -- (30:-1); \draw[red, thick] (-30:1) -- (-30:-1); \end{tikzpicture}}]{Images/imgf45204d3cc7af246fdfe39c1e2314fa7.svg}} \end{equation*}$$

In three dimensions, which is already harder to visualize, it turns out that the answer is six, attained by the six main diagonal lines of a regular icosahedron.

Let $N(d)$ denote the maximum number of equiangular lines in $\mathbb{R}^d$. Although the determination of each $N(d)$ turns out to be a finite problem, the complexity of the computation grows rapidly. The exact value of $N(d)$ is known for only finitely many $d$ (e.g., see GSY21).

A short and elegant linear algebraic argument by Gerzon LS73, reproduced in the footnote,⁠¹ shows that $N(d) \le \binom{d+1}{2}$. A matching quadratic lower bound $N(d) \ge c d^2$ was proved by de Caen dC00. Despite further progress, there remains a constant factor gap between the current lower and upper bounds.

¹

Let $v_1, \dots , v_n \in \mathbb{R}^d$ be unit vectors, one along each line, with pairwise inner products $\pm \alpha$. Let $w_i = v_i \otimes v_i \in \mathbb{R}^{d^2}$, which can be viewed as a symmetric $d\times d$ matrix, and thus determined by the $\binom{d+1}{2}$ entries on and above the diagonal. Thus $w_1, \dots , w_n$ lie in a $\binom{d+1}{2}$-dimensional vector space. Furthermore, $\langle w_i, w_j \rangle = \langle v_i, v_j \rangle ^2 = \alpha ^2$ if $i \ne j$, is equal to $1$ if $i = j$. The $n \times n$ matrix with $1$’s on the diagonal and $\alpha ^2$ elsewhere has full rank. So $w_1, \dots , w_n$ are linearly independent. Therefore $n \le \binom{d+1}{2}$.

✖

These constructions of quadratically many equiangular lines turn out to have pairwise angles approach $90^\circ$ as the dimension increases. What happens if we fix the angle and let the dimension grow?

Let $N_\alpha (d)$ be the maximum number of lines in $\mathbb{R}^d$ with pairwise angle $\cos ^{-1}\alpha$. The case of fixed $\alpha > 0$ and large $d$ is particularly interesting. It turns out that the number of lines grows linearly in $d$. More precisely, $N_\alpha (d) \le C_\alpha d$ for some constant $C_\alpha$ Buk16, in contrast to $N(d) = \Theta (d^2)$.

Question 1.

For fixed $0 < \alpha < 1$, determine $\lim _{d \to \infty } N_\alpha (d) / d$.

With Zilin Jiang, Jonathan Tidor, Yuan Yao, and Shengtong Zhang (students and a postdoc at MIT at the time of the work), we gave a complete answer to this question JTYZZ21. We will state the main results shortly. A key step in our solution is a new result in spectral graph theory concerning eigenvalue multiplicities. In this article, when we talk about the eigenvalues of a graph $G$, we are always referring to eigenvalues of the adjacency matrix $A_G$.

Theorem 2.

Every connected bounded degree graph has sublinear second eigenvalue multiplicity. More precisely, the second largest eigenvalue of the adjacency matrix of an $n$-vertex connected graph with maximum degree $\Delta$ has multiplicity $O_\Delta (n/\log \log n)$.

While much attention has been given to the spectral gap due to its connections to important properties like expansion and mixing (e.g., see the survey HLW06 on expander graphs), little is known about eigenvalue multiplicities. Theorem 2 is one of the first general results of this form. We will explore the eigenvalue multiplicity problem later in this article. It remains a tantalizing open problem to improve the bound of $O_\Delta (n/\log \log n)$ in Theorem 2. The best lower bound we know is on the order of $\sqrt {n/\log n}$.

History

While the general problem of equiangular lines has appeared in papers at least as early as the 1940s, the fixed angle version was considered in a 1973 paper by Lemmens and Seidel LS73, who determined the value of $N_{1/3}(d)$ for all $d$. In particular, they showed that

$$\begin{equation*} N_{1/3}(d) = 2(d-1) \quad \text{for all } d \ge 15. \end{equation*}$$

The next case was solved in a 1989 paper by Neumaier Neu89, who showed that

$$\begin{equation*} N_{1/5} (d) = \left\lfloor \frac{3}{2} (d-1) \right\rfloor \quad \text{for all sufficiently large $d$.} \end{equation*}$$

As for $N_{1/7}(d)$, Neumaier wrote in his paper that “the next interesting case will require substantially stronger techniques.”

Progress on this problem stalled until Bukh Buk16 reignited interest in the problem in his 2016 paper. He showed that $N_\alpha (d) \le C_\alpha d$ for some constant $C_\alpha$ for each $\alpha$. Bukh furthermore conjectured that $N_{1/(2k-1)}(d) = \frac{k}{k-1} d+ O_k(1)$ for any integer $k\ge 2$. This was followed by work by Balla, Dräxler, Keevash, and Sudakov BDKS18, who showed that

$$\begin{equation*} \limsup _{d \to \infty } N_\alpha (d)/d \le 1.99 \quad \text{for all }\alpha \ne 1/3. \end{equation*}$$

Jiang and Polyanskii JP20 formulated a conjecture for $\limsup _{d \to \infty } N_\alpha (d)/d$ as a function of $\alpha$. We defer the precise statement until Theorem 5 since it requires a new definition. They proved their conjecture for all $\alpha > (1 + 2\sqrt {2+\sqrt 5})^{-1} = 0.195\dots$, where the threshold comes from a problem they solved in spectral graph theory. They also explained why this is a natural barrier for all existing methods, clarifying Nermaier’s earlier comment. The missing key turned out to be sublinear second eigenvalue multiplicities (Theorem 2).

Results

Our work JTYZZ21 determined the limit of $N_\alpha (d)/d$ as $d \to \infty$ for all $\alpha$, confirming earlier conjectures of Bukh Buk16 and Jiang and Polyanskii JP20. For many values of $\alpha$, specifically those where the limit is greater than $1$, the theorem actually gives the exact value of $N_\alpha (d)$ for large $d$.

First, let us state the result when $1/\alpha$ is an odd integer, as the answer has a simpler form.

Theorem 3.

For every integer $k \ge 2$, there is some $d_0(k)$ so that

$$\begin{equation*} N_{1/(2k-1)} (d) = \left\lfloor \frac{k}{k-1} (d-1) \right\rfloor \qquad \text{for all } d \ge d_0(k). \end{equation*}$$

We now know that Theorem 3 holds for $d_0(k) = 2^{k^{Ck}}$ for some constant $C$ Bal21, whereas conjecturally $d_0(k) = k^C$ is enough. The bottleneck lies in improving Theorem 2.

To state the result for all other angles, we need some notation.

Definition 4.

The spectral radius order $k(\lambda )$ of $\lambda > 0$ is defined to be the minimum possible number of vertices of a graph with top eigenvalue $\lambda$. We set $k(\lambda ) = \infty$ if no such graph exists.

In other words, imagine enumerating all graphs in order of their number of vertices, computing the largest eigenvalue, and halting the first time $\lambda$ comes up. Then $k(\lambda )$ is the number of vertices in the corresponding graph.⁠² Now we are ready to state the main result from JTYZZ21. See Table 1 for examples.

²

The computation of $k(\lambda )$ given $\lambda$ is an interesting problem that we do not fully understand. For example, we do not know how to certify that some $\lambda$ has $k(\lambda ) = \infty$. There are some necessary conditions on $\lambda$ in order that $k(\lambda ) < \infty$. For example $\lambda$ should be a Perron number, namely a positive real algebraic integer whose Galois conjugates are all real and less than $\lambda$ in absolute value. However, being Perron is not sufficient for $k(\lambda ) < \infty$ Sch23.

✖

Table 1.

Examples for Theorem 5. Here $G$ is a graph on $k = k(\lambda )$ vertices with top eigenvalue $\lambda$.

$\alpha$	$\lambda$	$k$	$G$	$N_\alpha (d) \ \forall \text{ large } d$
$1/3$	$1$	$2$		$2(d-1)$
$1/5$	$2$	$3$		$\left\lfloor \frac{3}{2} (d-1) \right\rfloor$
$1/7$	$3$	$4$		$\left\lfloor \frac{4}{3} (d-1) \right\rfloor$
$1/(2k-1)$	$k-1$	$k$	$K_k$	$\left\lfloor \frac{k}{k-1} (d-1) \right\rfloor$
$1/(1+2\sqrt {2})$	$\sqrt {2}$	$3$		$\left\lfloor \frac{3}{2} (d-1) \right\rfloor$

Theorem 5.

Let $0 < \alpha < 1$. Let $\lambda = (1-\alpha )/(2\alpha )$ and $k = k(\lambda )$ be the spectral radius order.

(a)

If $k < \infty$, then there is some $d_0(\alpha )$ so that$$\begin{equation*} N_\alpha (d) = \left\lfloor \frac{k}{k-1}(d-1) \right\rfloor \qquad \text{for all } d \ge d_0(\alpha ). \end{equation*}$$

(b)

If $k = \infty$, then$$\begin{equation*} N_\alpha (d) = d+ o(d) \qquad \text{as } d \to \infty . \end{equation*}$$

Connection to Spectral Graph Theory

The classic Algebraic Graph Theory (Graduate Text in Mathematics) by Godsil and Royle dedicates an entire chapter to equiangular lines, which the authors call “one of the founding problems of algebraic graph theory.” Let us explain the connection between equiangular lines and spectral graph theory.

Given equiangular lines $\ell _1, \dots , \ell _n$ in $\mathbb{R}^d$, pick a unit vector $v_i$ along the direction of $\ell _i$ for each $i$. There are two choices for $v_i$. We make the choice arbitrarily for now and revisit this choice later. Since the lines pairwise form angle $\theta = \cos ^{-1}\alpha$, we have $\left\langle v_i, v_j \right\rangle = \pm \alpha$ for all $i \ne j$. Define a graph $G$ with vertices $1, \dots , n$, and an edge between $i$ and $j$ if $\left\langle v_i, v_j \right\rangle = -\alpha$.

The Gram matrix has ones on the diagonal and $\pm \alpha$ off diagonal, with signs determined by the graph $G$: (here $I$ is the identity matrix and $J$ is the all-ones matrix)

$$\begin{align*} \text{Gram matrix} &= \begin{pmatrix} \left\langle v_1, v_1 \right\rangle & \cdots & \left\langle v_1, v_n \right\rangle \\ \vdots & \ddots & \vdots \\ \left\langle v_n, v_1 \right\rangle & \cdots & \left\langle v_n, v_n \right\rangle \end{pmatrix} \\ &= (1 - \alpha ) I - 2\alpha A_G + \alpha J. \end{align*}$$

The Gram matrix has rank at most $d$, since $v_1, \dots , v_n \in \mathbb{R}^d$. Furthermore, the Gram matrix is positive semidefinite. Conversely, any positive semidefinite $n \times n$ matrix with rank at most $d$ and ones on the diagonal is the Gram matrix of some collection of unit vectors in $\mathbb{R}^d$. Indeed, we can recover $v_1, \dots , v_n$ up to isometry from their Gram matrix using the Cholesky decompostion.

Via the above correspondence, for a given $\alpha$ and $d$, the following two quantities are both equal to $N_\alpha (d)$:

(a)

the maximum number of lines in $\mathbb{R}^d$ with pairwise angle $\cos ^{-1}\alpha$;

(b)

the maximum number of vertices of a graph $G$ for which$$\begin{equation*} (1-\alpha ) I - 2\alpha A_G + \alpha J \end{equation*}$$

is positive semidefinite and has rank at most $d$.

Proof Outline

Lower bound constructions for $N_\alpha (d)$

As an example, let us show

$$\begin{equation*} N_{1/5}(2\ell + h + 1) \ge 3\ell + h \qquad \text{for integers }\ell , h \ge 0. \end{equation*}$$

We need to exhibit $3\ell + h$ unit vectors in $\mathbb{R}^{2\ell + h + 1}$ with pairwise inner products $\pm 1/5$. Rather than providing the coordinates of the vectors, which would be quite unwieldy, it suffices to provide their Gram matrix. The associated graph $G$ turns out to be a disjoint union of $\ell$ triangles along with $h$ isolated vertices.

$$\begin{equation*} \vcenter{\img[][220pt][34pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[v/.style={circle, fill, minimum size = 3pt,inner sep = 0pt}, scale=.7 ] \foreach\i in {0, 3, 8}{ \begin{scope}[xshift={\i cm}] \node[v] (a) at (90:1) {}; \node[v] (b) at (210:1) {}; \node[v] (c) at (-30:1) {}; \draw(a)--(b)--(c)--(a); \end{scope} \node at (5.7,0.2) {$\cdots$}; } \node[v] at (10,0.5) {}; \end{tikzpicture}}]{Images/img6b2e7bda3666db76b768ea847f2b9b9b.svg}} \end{equation*}$$

It remains to verify that the associated matrix

$$\begin{equation*} (1 - \alpha ) I - 2\alpha A_G + \alpha J = (4I - 2A_G + J)/5 \end{equation*}$$

is positive semidefinite and has rank at most $2\ell + h + 1$. Indeed, positive semidefiniteness follows from being a positive linear combination of

•

$2I - A_G$, which is positive semidefinite since the top eigenvalue of a triangle is $2$, and

•

$J$, which is also positive semidefinite.

As for rank, each of the $\ell$ triangle components of $2I - A_G$ contributes a new dimension to its kernel. So the dimension of the kernel is $\operatorname {nullity}(2I - A_G) = \ell$. Thus $\operatorname {rank}(2I - A_G) = 2\ell + h$. Since $\operatorname {rank}J = 1$, we have $\operatorname {rank}(2I - A_G + J) \le 2\ell + h +1$. This finishes the proof of $N_{1/5}(2\ell + h + 1) \ge 3\ell + h$.

The same argument shows the general lower bound $N_\alpha (d) \ge \left\lfloor \frac{k}{k-1}(d-1) \right\rfloor$ from Theorem 5.

Upper bound on $N_\alpha (d)$

Applying the rank–nullity theorem, we have

$$\begin{equation*} n = \operatorname {rank}(\text{Gram matrix}) + \operatorname {nullity}(\text{Gram matrix}). \end{equation*}$$

The rank of the Gram matrix is at most $d$ since the vectors live in $\mathbb{R}^d$. Since $\operatorname {rank}J = 1$,

$$\begin{align*} \MoveEqLeft \mathrm{nullity}(\text{Gram matrix}) \\ &= \mathrm{nullity}((1-\alpha )I - 2\alpha A_G + \alpha J) \\ &\le \mathrm{nullity}((1-\alpha )I - 2\alpha A_G) + 1 \\ &= \mathrm{mult}(\lambda , G) + 1, \end{align*}$$

where $\mathrm{mult}(\lambda , G)$ denotes the multiplicity of $\lambda = (1-\alpha )/(2\alpha )$ as an eigenvalue of $A_G$. Already we see the connection between equiangular lines and eigenvalue multiplicities.

The graph $G$ cannot have more than one eigenvalue greater than $\lambda$. Indeed, otherwise their span would contain a unit vector $w$ satisfying $\left\langle w, A_Gw \right\rangle > \lambda$ and $\left\langle w, \mathbf{1} \right\rangle = 0$. It would contradict the positive semidefiniteness of the Gram matrix as

$$\begin{align*} \MoveEqLeft \left\langle w, (\text{Gram matrix})w \right\rangle \\ &= \left\langle w, ((1-\alpha ) I - 2\alpha A_G + \alpha J) w \right\rangle \\ & < 1-\alpha - 2\alpha \lambda < 0. \end{align*}$$

Thus, for $\lambda$ to be an eigenvalue of $G$, we must be in one of the following two situations:

(a)

$\lambda$ is the largest eigenvalue of $G$. In the more interesting case of $k = k(\lambda ) < \infty$, this case turns out to produce the equality case when the dimension $d$ is large. The optimal $G$ giving the maximal value of $\operatorname {mult}(\lambda ,G)$ ends up being a disjoint union of small graphs each with top eigenvalue at most $\lambda$. This matches the lower bound construction from earlier, giving $n = \left\lfloor k(d-1)/(k-1) \right\rfloor$. This case is easy to analyze. We skip the details and refer the readers to JTYZZ21.

(b)

$\lambda$ is the second largest eigenvalue of $G$. This is the harder and more interesting case. The crux of the argument is to show that this case is suboptimal when the dimension $d$ is large. Note that this situation could indeed occur for optimal configurations in small dimensions, such as constructions giving $N(d) = \Theta (d^2)$.

We want to show that the second largest eigenvalue of $A_G$ has small multiplicity. By a short argument that we omit, we can assume that $G$ is connected. Not all connected graphs have small second eigenvalue multiplicity. For example, a clique on $n$ vertices has top eigevalue $n-1$ with multiplicity $1$, and all $n-1$ remaining eigenvalues equal to $-1$.

Balla et al. BDKS18 observed some important constraints on $G$. Recall that in constructing $G$ from a set of equiangular lines, we took one unit vector $v$ along each line. In doing so, we made an arbitrary choice whether to take $v$ or $-v$. Recall that the edges of $G$ correspond to inner product $-\alpha$ while nonedges correspond to inner product $\alpha$. Switching some vector to its negative changes the graph by swapping all the edges and nonedges out of the corresponding vertex.

$$\begin{equation*} \vcenter{\img[][227pt][47pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture} [v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, d/.style={diamond, fill, red, minimum size = 6pt,inner sep = 0pt}, scale=.9, font=\footnotesize] \begin{scope}[xshift=0cm] \node[d] (1) at (180:1) {}; \foreach\i in {2,...,6} \node[v] (\i) at (240-60*\i:1) {}; \draw(1)--(2) (1)--(3) (2)--(3) (3)--(4) (4)--(5)--(6) (3)--(5); \draw[-stealth,red,thick] (-1.5,0) node[left]{$v$} -- ++(60:.5); \end{scope} \draw[decorate, decoration={snake, amplitude=0.5mm}, ->,blue,thick] (1.5,0)-- node[above,red]{$v \mapsto-v$} (3.8,0); \begin{scope}[xshift=6cm] \node[d] (1) at (180:1) {}; \foreach\i in {2,...,6} \node[v] (\i) at (240-60*\i:1) {}; \draw(1)--(4)(1)--(5)(1)--(6) (2)--(3) (3)--(4) (4)--(5)--(6) (3)--(5); \draw[-stealth,red,thick] (-1.5,0) node[left]{$v$} -- ++(60:-.5); \end{scope} \end{tikzpicture}}]{Images/img78087664d28714bd104fa91ac6f264ce.svg}} \end{equation*}$$ It turns out that one can always switch the graph to get bounded maximum degree. Here is a precise statement taken from JTYZZ21, based on BDKS18. We will sketch a proof in the next section.

Theorem 6 (Switching to bounded degree).

For every $\alpha$, there exists $\Delta$ that depends on $\alpha$ only, so that given any configuration of lines (in any dimension) with pairwise angle $\cos ^{-1}\alpha$, we can choose one unit vector along each line so that each of these unit vectors has inner product $-\alpha$ with at most $\Delta$ other unit vectors.

To complete the proof of Theorem 5 on the maximum number of equiangular lines with a fixed angle, recall we are left with the case when $\lambda$ is the second largest eigenvalue of a connected graph $G$. By Theorem 6, we can assume that $G$ has bounded degree. By Theorem 2, we have $\mathrm{mult}(\lambda , G) = o(n)$. So $n \le d + \mathrm{mult}(\lambda , G) + 1 = d + o(n)$, and thus $n \le d + o(d)$. When $k = k(\lambda ) < \infty$, having $n \le d + o(d)$ is suboptimal compared to the case of $\lambda$ being the largest eigenvalue of $G$, in which the optimal value is $n = \left\lfloor k(d-1)/(k-1) \right\rfloor$.

Switching to a Bounded Degree Graph

Let us sketch the proof of Theorem 6. We start with unit vectors $v_1, \dots , v_n \in \mathbb{R}^d$ with pairwise inner products $\pm \alpha$. We form the “negative graph” $G$ with vertices $\{1, \dots , n\}$, where $ij$ is an edge if $\left\langle v_i, v_j \right\rangle = -\alpha$. We want to show that we can negate some subset of vectors to turn $G$ into a bounded degree graph. Flipping each $v_i$ to $-v_i$ has the effect of interchanging the neighborhood and non-neighborhood of vertex $i$.

Forbidden induced subgraphs

We start by identifying two types of forbidden induced subgraphs of $G$, using the positive-semidefiniteness of $G$:

(I)

Large clique;

(II)

Some vertex $u$, two large subsets $A$ and $B$ with no edges between them, such that $u$ is complete to $A$ and empty to $B$ (i.e., no edges between $u$ to $B$).

$$\begin{equation*} \vcenter{\img[][60pt][59pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, font=\footnotesize, baseline={([yshift=-.5ex]current bounding box.center)}] \foreach\i in {0,...,7} \node[v] (\i) at (45*\i:1) {}; \foreach\i in {0,...,7}{ \foreach\j in {0,...,7}{ \ifnum\i<\j\relax \draw(\i) -- (\j); \fi } } \end{tikzpicture}}]{Images/img1a44675e88368ffe2a8b8636e4ce1b29.svg}} \qquad \vcenter{\img[][156pt][130pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[v/.style={circle, fill, minimum size = 3pt,inner sep = 0pt}, scale=.7, font=\footnotesize, baseline={([yshift=-.5ex]current bounding box.center)}] \node[v,label=left:$u$] (u) at (0,5) {}; \coordinate(a) at (-2,0); \begin{scope}[shift=(a)] \coordinate(a1) at (-40:1); \coordinate(a2) at (-40:-1); \coordinate(a3) at (90:.8); \coordinate(a4) at (90:-.8); \end{scope} \coordinate(b) at (2,0); \begin{scope}[shift=(b)] \coordinate(b1) at (40:1); \coordinate(b2) at (40:-1); \coordinate(b3) at (90:.8); \coordinate(b4) at (90:-.8); \end{scope} \draw[fill=black] (u) -- (a1)--(a2) --cycle; \draw(u) -- (b1)--(b2) --cycle; \draw(b3)--(b4)--(a4)--(a3)--cycle; \draw[fill=pink!30] (a) circle (1.4) node[label={[label distance=8mm]left:$A$}]{$?$}; \draw[fill=pink!30] (b) circle (1.4) node[label={[label distance=8mm]right:$B$}]{$?$}; \end{tikzpicture}}]{Images/img5b1006584eca3ef6ed422111273b1eb5.svg}} \end{equation*}$$

Here “large” means a large constant. We will be rather imprecise with constants and quantifiers in this proof sketch, so as to not be bogged down by details.

Let us first address (I). The Gram matrix restricted to an $\ell$-vertex clique is

$$\begin{equation*} \begin{pmatrix} 1 & -\alpha & \cdots & -\alpha \\ -\alpha & 1 & \cdots & -\alpha \\ \cdots & \cdots & \ddots & \vdots \\ -\alpha & -\alpha & \cdots & 1 \end{pmatrix}. \end{equation*}$$

The sum of entries is $\ell - \ell (\ell -1)\alpha$, which must be nonnegative due to the matrix being positive semidefinite. So $\ell \le 1 + 1/\alpha$. In other words, $G$ has no clique on more than $1 + 1/\alpha$ vertices.

The proof of (II) is based on a similar idea except that we need a slightly more complicated test vector for positive semidefiniteness. The Gram matrix restricted to $\left\{ u \right\} \cup A \cup B$ is

$$\begin{equation*} \left( \begin{array}{c|ccc|ccc} 1 & -\alpha & \cdots & -\alpha & \alpha & \cdots & \alpha \\\hline -\alpha & 1 & & ? & 1 & & \alpha \\\vdots & & \ddots & & & \ddots & \\-\alpha & ? & & 1 & \alpha & & 1 \\\hline \alpha & 1 & & \alpha & 1 & & ? \\\vdots & & \ddots & & & \ddots &\\\alpha & \alpha & & 1 & ? & & 1 \end{array} \right) \end{equation*}$$

Our test vector $v$ assigns a small constant $\epsilon > 0$ to $u$, as well as $1/\left\lvert A\right\rvert$ to each vertex of $A$, and likewise $1/\left\lvert B\right\rvert$ to each vertex of $B$. Then

$$\begin{align*} v^\intercal M v &\approx \begin{pmatrix} \epsilon \\ 1 \\ -1 \end{pmatrix}^\intercal \begin{pmatrix} 1 & -\alpha & \alpha \\ -\alpha & \star & \alpha \\ \alpha & \alpha & \star \end{pmatrix} \begin{pmatrix} \epsilon \\ 1 \\ -1 \end{pmatrix} \\ &= 2(\star - \alpha ) - 2\epsilon \alpha + \epsilon ^2 < 0. \end{align*}$$

Here $\star \in [-\alpha ,\alpha ]$. The first approximation ignores the negligible contributions from diagonal matrix entries, which is valid if $A$ and $B$ are large compared to $1/\epsilon$.

Switching argument

Using the above forbidden induced subgraphs, let us now argue that $G$ can be switched to a bounded degree graph.

By Ramsey’s theorem,⁠³ not having a large clique implies that we must have a large independent set $S$, whose size grows with $n$.

³

Balla Bal21 later found another proof not using Ramsey’s theorem, leading to a better quantitative result. We now know that, in Theorem 6, one can take $\Delta$ to be $O(\alpha ^{-4})$.

✖

Consider any vertex $u$ outside $S$. We claim that $u$ has either a bounded number of neighbors in $S$ or a bounded number of non-neighbors in $S$. Indeed, let $A$ and $B$ be respectively the neighbors and non-neighbors of $u$ in $S$. There are no edges between $A$ and $B$ since they are both contained in the independent set $S$. If $A$ and $B$ were both large, then together with $u$ they would form a type II forbidden configuration.

Thus, for every vertex $u$ outside $S$, by negating the vector corresponding to $u$ if necessary, we may assume that $u$ has only a bounded number of neighbors in $S$.

Finally, we claim that the resulting graph has bounded degree. Suppose some vertex $u$ has many neighbors. Let $A$ be a large but bounded subset of neighbors of $u$. Recall that each vertex in $A$ has a bounded number of neighbors in $S$. Let $B$ be $S$ minus the neighborhood of $\left\{ u \right\}\cup A$. Then $u, A, B$ would once again violate (II).

Sublinear Second Eigenvalue Multiplicity

Let us now discuss Theorem 2. It says that a connected $n$-vertex graph with maximum degree⁠⁴ $\Delta$ has second eigenvalue multiplicity at most $O_\Delta (n / \log \log n)$. Before diving into the proof, let us discuss some near-miss examples that illustrate the necessity of the hypotheses.

⁴

We view $\Delta$ as a constant, though the dependence on $\Delta$ is quite mild as the hidden leading constant is $O(\log \Delta )$.

✖

Bounded degree. A complete graph on $n$ vertices has second eigenvalue multiplicity $n-1$. Other examples with linear eigenvalue multiplicity include strongly regular graphs, such as Paley graphs.

Connectedness. A disjoint union of $n/2$ edges has top eigenvalue $1$ repeated $n/2$ times. So the theorem is false without the connectivity hypothesis.

Second eigenvalue. The following graph has eigenvalue 0 with linear multiplicity. One such eigenvector is shown (unlabeled vertices are set to zero).

$$\begin{equation*} \vcenter{\img[][216pt][25pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, scale=0.5 ] \foreach\i in {0,1,2,5,6,7} { \begin{scope}[xshift=\i*2cm] \node[v] (\i) at (0,0) {}; \node[v] (\i0) at (-.5,1) {}; \node[v] (\i1) at ( .5,1) {}; \draw(\i)--(\i0); \draw(\i)--(\i1); \end{scope} } \node[font=\tiny,inner sep=0pt, baseline=0pt] at ( 3.3,1.5) {$-1$}; \node[font=\tiny,inner sep=0pt, baseline=0pt] at (4.2,1.5) {$\phantom{+}1$}; \draw(0)--(1)--(2) (5)--(6)--(7); \draw(2) -- ++(1,0); \draw(5) -- ++(-1,0); \node at (7.1,.5) {$\cdots$}; \end{tikzpicture}}]{Images/img6ca34d147553b73eba141a867adccd39.svg}} \end{equation*}$$

Furthermore, here is a graph whose least eigenvalue $-3$ has linear multiplicity, arising from the eigenvector of $K_{3,3}$ with eigenvalue $-3$.

$$\begin{equation*} \vcenter{\img[][219pt][45pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, scale=0.5 ] \foreach\i in {0,1,2,5,6,7} { \begin{scope}[xshift=\i*2cm] \node[v] (\i) at (0,0) {}; \foreach\j in {1,2,3}{ \node[v] (\i\j0) at (-.6,\j) {}; \node[v] (\i\j1) at ( .6,\j) {}; } \foreach\j in {1,2,3} \foreach\k in {1,2,3} \draw(\i\j0)--(\i\k1); \draw(\i)--(\i10); \draw(\i)--(\i11); \end{scope} } \draw(0)--(1)--(2) (5)--(6)--(7); \draw(2) -- ++(1,0); \draw(5) -- ++(-1,0); \node at (7.1,1) {$\cdots$}; \end{tikzpicture}}]{Images/img6137e062df455fffe9c10e88b3e2241a.svg}} \end{equation*}$$

So Theorem 2 is really about the top of the spectrum. Essentially the same proof shows that for any constant $j$, the $j$-th largest eigenvalue of a connected graph with maximum degree $\Delta$ has multiplicity $O_{\Delta , j}(n/\log \log n)$.

Proof of sublinear second eigenvalue multiplicity

Let us prove that $\operatorname {mult}(\lambda , G) = O_\Delta (n/\log \log n)$ for a connected $n$-vertex graph $G$ with maximum degree $\Delta$ and second largest eigenvalue $\lambda$. We use the trace method to bound eigenvalue multiplicities. Write $\lambda _1(G) \ge \cdots \ge \lambda _n(G)$ for the eigenvalues of $A_G$, including multiplicities. We have

$$\begin{equation*} \operatorname {mult}(\lambda , G) \lambda ^{2s} \le \sum _{i=1}^n \lambda _i(G)^{2s} = \operatorname {tr}A_G^{2s}. \end{equation*}$$

The first inequality is quite wasteful and so the inequality on its own is not enough to give a sublinear bound on $\operatorname {mult}(\lambda , G)$. The right-hand side counts closed walks of length $2s$ in $G$. Such a walk must stay in the radius $s$ neighborhood of its starting vertex. This leads us to examine the spectral radius of balls in $G$, which we refer to informally as a “local spectral radius.” See Figure 1.

Figure 1.

A key idea in the proof of Theorem 2 is that removing a net of vertices (white dots) significantly lowers local spectral radii ($\lambda _1$ of the dark disk).

A key new idea is to delete a small net from the graph. An $r$-net in a graph $G$ is a subset of vertices such that every vertex in $G$ lies within distance $r$ from some vertex in the $r$-net. We show that deleting a net significantly reduces local spectral radii. This observation combined with the earlier inequality yields a good upper bound on the multiplicity of $\lambda$ in $G$ with the net removed. Finally, to bound $\operatorname {mult}(\lambda , G)$, observe that by the Cauchy eigenvalue interlacing theorem, deleting $h$ vertices can reduce each eigenvalue multiplicity by at most $h$.

Lemma 7 (Finding a small net).

For every $n$ and $r$, every connected $n$-vertex graph has an $r$-net of size at most $\left\lceil n/(r+1) \right\rceil$.

$$\begin{equation*} \vcenter{\img[][216pt][93pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[ v/.style={circle, fill, minimum size = 3pt,inner sep = 0pt}, b/.style={regular polygon, regular polygon sides = 3,blue,fill, minimum size = 7pt,inner sep = 0pt}, s/.style={star,red,fill, minimum size = 6pt,inner sep = 0pt}, r/.style={circle, red,draw, minimum size = 4pt,inner sep = 0pt}, rr/.style={rectangle,red,draw, minimum size = 5pt,inner sep = 0pt}, baseline={([yshift=-.8ex]current bounding box.center)}, font=\footnotesize ] \fill[pink] (4.7,.7) circle (2.2 and 1.5); \node[b,label={[blue]left:root}] (0) at (0,0) {}; \node[v] (00) at (1,1) {}; \node[v] (01) at (1,-1) {}; \node[v] (000) at (2,1.5) {}; \node[v] (001) at (2,0.5) {}; \node[s,label={[red]90:$u$}] (0010) at (3,0.5) {}; \node[v] (0011) at (3,-.5) {}; \node[r] (00101) at (4,-.2) {}; \node[v] (00110) at (2.5,-1) {}; \node[v] (00111) at (3.5,-1) {}; \node[r] (00100) at (4,0.5) {}; \node[r] (001000) at (5,1) {}; \node[r] (001001) at (5,0) {}; \node[rr] (0010000) at (6,1) {}; \draw[line width=.3mm] (0)--(00)--(000) (00)--(001)--(0010)--(00100)--(001000)--(0010000) (0010)--(00101) (00100)--(001001) (001)--(0011)--(00110) (0011)--(00111) (0)--(01); \end{tikzpicture}}]{Images/img6f03bd76a8d311a5e093ac257be057dd.svg}} \end{equation*}$$

Proof.

First replace the graph by a spanning tree. Pick an arbitrary vertex as the root. Pick a vertex furthest from the root, and walk $r$ steps towards the root to end up at vertex $u$. Add $u$ to the net and keep only the the subtree containing the root after deleting $u$. This removes at least $r+1$ vertices. Repeat.

Lemma 8 (Net removal reduces spectral radius).

If $H$ (with at least one vertex) is obtained from $G$ by deleting an $r$-net, then $\lambda _1(H)^{2r} \le \lambda _1(G)^{2r} - 1$.

Proof.

We can assume that $G$ has no isolated vertices. Write $A_G$ for the adjacency matrix of $G$, and $A_H$ the matrix obtained by zeroing out the rows and columns corresponding to vertices of the deleted net. Clearly $A_H^{2r} \le A_G^{2r}$ entrywise. Let $v$ be a vertex of $G$. Consider the diagonal entries indexed by $(v,v)$ in $A_H^{2r}$ and $A_G^{2r}$. They count closed walks of length $2r$ starting at $v$. There are always strictly more such walks in $G$ than in $H$ since at least one such walk passes through the net. Thus $A_H^{2r} \le A_G^{2r} - I$ entrywise, and the lemma follows.

Let us write