On the principal eigenvector of a graph

Yueheng Zhang The University of Chicago

(Date: Jul 29, 2021)

Abstract.

The principal ratio of a connected graph $G$ , $\gamma(G)$ , is the ratio between the largest and smallest coordinates of the principal eigenvector of the adjacency matrix of $G$ . Over all connected graphs on $n$ vertices, $\gamma(G)$ ranges from $1$ to $n^{cn}$ . Moreover, $\displaystyle{\gamma(G)=1}$ if and only if $G$ is regular. This indicates that $\gamma(G)$ can be viewed as an irregularity measure of $G$ , as first suggested by Tait and Tobin (El. J. Lin. Alg. 2018). We are interested in how stable this measure is. In particular, we ask how $\gamma$ changes when there is a small modification to a regular graph $G$ . We show that this ratio is polynomially bounded if we remove an edge belonging to a cycle of bounded length in $G$ , while the ratio can jump from $1$ to exponential if we join a pair of vertices at distance $2$ . We study the connection between the spectral gap of a regular graph and the stability of its principal ratio. A naive bound shows that given a constant multiplicative spectral gap and bounded degree, the ratio remains polynomially bounded if we add or delete an edge. Using results from matrix perturbation theory, we show that given an additive spectral gap greater than $(2+\epsilon)\sqrt{n}$ , the ratio stays bounded after adding or deleting an edge.

Written for the University of Chicago 2019 Math REU; mentored by Professor László Babai.

1. Introduction

It is known that the adjacency matrix of every connected graph has a simple largest eigenvalue, and this eigenvalue has an eigenvector with all-positive coordinates, called the principal eigenvector of the graph. It is natural to study how this eigenvector reflects the structure of the graph. Our goal is to obtain asymptotic information as the number of vertices approaches infinity in a family of graphs.

Cioabă and Gregory [6] defined the principal ratio of the graph $G$ , $\gamma(G)=q_{\max}/q_{\min}$ , to be the ratio between the largest and smallest coordinates of the principal eigenvector $\mathbf{q}$ . This ratio is $1$ for regular graphs, while it can grow at factorial rate (i.e., $\gamma(G)>n^{cn}$ for some positive constant $c$ ) [6]. Since $\gamma(G)\geq 1$ where equality holds if and only if $G$ is regular, it is natural to think of $\gamma(G)$ as a measure of the irregularity of $G$ . This view was suggested by Tait and Tobin [8].

A basic observation is that, given a connected graph $G$ with largest eigenvalue $\lambda_{1}$ and diameter $D$ , the principal ratio satisfies

(1.1)

\gamma(G)\leq\lambda_{1}^{D}.

We are interested in the stability of $\gamma$ , i.e., how a slight change of $G$ influences $\gamma(G)$ . In particular, given a $d$ -regular graph $G$ , we ask how $\gamma(G)$ changes from the constant $1$ if we add or remove one edge in $G$ . (We call the resulting graphs $G+e$ and $G-e$ , respectively.) We always assume the edge we remove will not disconnect $G$ (i.e., the edge $e$ is not a bridge), so that the principal eigenvector of $G-e$ is defined.

In Section 4, we study the cases where the edge we add to or remove from a regular graph is between vertices at bounded distance. We show the following.

•

$\gamma(G+e)$ can jump to exponential in $n$ when the degree is bounded [Theorem 4.3]. In our example, $e$ connects two vertices at distance $2$ in $G$ . We make use of Chebyshev polynomials in proving this result. We recall some properties of Chebyshev polynomials and show their connection with the principal eigenvectors of certain graphs in Sec. 3.2.
It is easy to infer from (1.1) that boundedness of the degree is necessary here (see Cor. 3.4 and Fact 3.5).
•

If we remove an edge belonging to a cycle of bounded length in $G$ , then $\gamma(G-e)$ is always polynomially bounded regardless of the degree [Theorem 4.11].

We also study the relevance of the spectral gap to the stability of $\gamma(G)$ for regular graphs. In Section 5, based on (1.1), we note the following.

•

$\gamma(G\pm e)$ is always polynomially bounded in $n$ when $G$ is a bounded-degree expander graph, i.e., when the degree is bounded and the spectral gap of $G$ is bounded away from zero [Observation 5.3].

In Section 6.2, we put this problem in the more general context of perturbations of matrices. By adapting theorems and proofs from Stewart and Sun’s book [3] to our special case, we show the following.

•

If the additive spectral gap is greater than $(2+\epsilon)\sqrt{n}$ , then $\gamma(G\pm e)$ is bounded [Theorem 6.1].

This result does not follow from (1.1). Indeed, in Section 6.1 we construct graphs with degree of order $n^{(2+t)/3}$ and additive spectral gap of order $n^{t}$ , having diameter of order $n^{(1-t)/3}$ , for any constant $0<t<1$ . Similar applications of matrix perturbation theory in link analysis for networks can be found in [5].

The main technical results of this paper are the first and the fourth bullet points.

2. General preliminaries

2.1. Graphs

By a graph we mean what is often called a simple graph (undirected graph with no self-loops and no parallel edges). $G$ will always denote a connected graph with $n$ vertices. We denote by $V(G)$ and $E(G)$ the set of vertices and edges of $G$ , respectively. We usually identify the set of vertices with the set $[n]=\{1,2,\dots,n\}$ . We write $i\sim_{G}j$ if vertices $i,j$ are adjacent in $G$ . We denote by $N_{G}(j)$ the set of neighbors of $j$ in $G$ . We use $\deg_{G}(j)$ to denote the degree of vertex $j$ in $G$ . We write $\overline{G}$ for the complement of $G$ . We let $\operatorname{dist}_{G}(i,j)$ denote the distance between vertices $i$ and $j$ in $G$ , and $D(G):=\max_{i,j}\operatorname{dist}(i,j)$ the diameter of $G$ .

Let $C_{n}$ denote the cycle with $n$ vertices. Let $P_{r}$ denote the path with $r$ vertices; it has $r-1$ edges. Let $K_{s}$ denote the clique with $s$ vertices; it has $\binom{s}{2}$ edges. Following the notation used in previous papers on this subject, we use $P_{r}\cdot K_{s}$ to denote the graph obtained by merging the vertex at one end of $P_{r}$ with one vertex in $K_{s}$ . So $P_{r}\cdot K_{s}$ has $n=r+s-1$ vertices, $r-1+\binom{s}{2}$ edges, and diameter $r$ . This has been called a kite graph or a lollipop graph. We will call it a kite graph.

2.2. Matrices, spectra

Orthonormality in $\mathbb{R}^{n}$ refers to the standard dot product. Given a matrix $A$ , we write $a_{ij}$ for the entry on the $i$ -th row and in the $j$ -th column of $A$ , and we write $A=(a_{ij})$ .

We use $M_{n}(\mathbb{R})$ to denote the set of $n\times n$ real matrices. We write $\mathbf{j}_{n}$ for the all-ones vector in $\mathbb{R}^{n}$ , and $J_{n}$ for the $n\times n$ all-ones matrix. We omit the dimension when it is clear from context.

For an $m\times n$ real matrix $M$ , we write $\|M\|$ for the operator norm of $M$ induced by $\ell^{2}$ vector norm ( $\|\cdot\|$ ),

\|M\|=\sup_{\mathbf{x}\in\mathbb{R}^{n},\;\mathbf{x}\neq\mathbf{0}}\frac{\|M\mathbf{x}\|}{\|\mathbf{x}\|}.

In the rest of Sec. 2.2, $A=(a_{ij})$ will always denote a real symmetric $n\times n$ matrix with eigenvalues $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$ .

Definition 2.1.

A multiset based on a set $A$ is a function from $A$ to positive integers, denoted by $\displaystyle{\{\{a^{m(a)}\mid a\in A\}\}}$ . The value $m(a)$ is called the multiplicity of the element $a$ . For example, $\{\{a^{3},b,c^{2}\}\}$ . We also expand this notation to $\{\{a,a,a,b,c,c\}\}$ . The order in which the elements are listed does not matter. So, for instance,

\{\{a^{3},b,c^{2}\}\}=\{\{c^{2},b,a^{3}\}\}=\{\{a,a,a,b,c,c\}\}=\{\{a,b,c,a,a,c\}\}.

Definition 2.2.

The spectrum of an $n\times n$ matrix $M$ is the multiset of its eigenvalues. We denote it by $\operatorname{spec}(M)$ .

Fact 2.3.

The spectrum of the cycle $C_{r}$ is

.

\left\{\left\{2\cos\left(\frac{2\pi j}{r}\right)\bigg{|}\>j=0,1,\dots,r-1\right\}\right\}.\qed

Notation 2.4.

Let $B=(b_{ij})$ be an $m\times n$ matrix and let $M$ be a $p\times q$ matrix. The Kronecker product of $B$ and $M$ , $B\otimes M$ , is the $mp\times nq$ matrix

\begin{pmatrix}b_{11}M&b_{12}M&\cdots&b_{1n}M\\ b_{21}M&b_{22}M&\cdots&b_{2n}M\\ \vdots&\vdots&\vdots&\vdots\\ b_{m1}M&b_{m2}M&\cdots&b_{mn}M\end{pmatrix}.

Fact 2.5.

Let $B\in M_{n}(\mathbb{R})$ and $M\in M_{m}(\mathbb{R})$ . Let the eigenvalues of $B$ be $\displaystyle{\lambda_{1}\geq\cdots\geq\lambda_{n}}$ and let the eigenvalues of $M$ be $\displaystyle{\mu_{1}\geq\cdots\geq\mu_{m}}$ . Then

.

\operatorname{spec}(B\otimes M)=\{\{\lambda_{i}\mu_{j}\mid i\in[n],\>j\in[m]\}\}.\qed

2.3. The adjacency operator, principal eigenvector and eigenvalue

We write $A_{G}$ to denote the adjacency matrix of a graph $G$ . We note that $A_{G}$ is a real symmetric matrix, so its eigenvalues are real. We refer to the eigenvalues and eigenvectors of $A_{G}$ as the eigenvalues and eigenvectors of the graph $G$ , respectively. We write $\lambda_{1}(G)\geq\lambda_{2}(G)\geq\cdots\geq\lambda_{n}(G)$ to denote the eigenvalues of $G$ .

Fact 2.6.

For every connected graph $G$ , the largest eigenvalue $\lambda_{1}(G)$ is simple, and it has a unique-up-to-scaling all-positive eigenvector (the principal eigenvector). ∎

We write $\mathbf{q}(G)$ for the principal eigenvector of $G$ scaled to have $\ell^{2}$ norm $1$ . Let $q_{i}(G)$ denote the coordinate corresponding to vertex $i$ in $\mathbf{q}(G)$ . We write $q_{\max}(G)$ and $q_{\min}(G)$ for the maximum and minimum coordinates of $\mathbf{q}(G)$ , and $v_{\max}(G)$ and $v_{\min}(G)$ for corresponding vertices. Recall that the principal ratio of $G$ is defined as

(2.1)

\gamma(G):=\frac{q_{\max}(G)}{q_{\min}(G)}.

In the rest of Sec. 2.3, we fix the graph $G$ and omit it from notations.

Observation 2.7.

Given $\mathbf{y}=(y_{1},\dots,y_{n})$ , the $i$ -th coordinate of $A\mathbf{y}$ is given by

.

(A\mathbf{y})_{i}=\sum_{j:i\sim j}y_{j}.\qed

Corollary 2.8.

$\mathbf{y}=(y_{1},\dots,y_{n})$ is an eigenvector of $A$ to eigenvalue $\rho$ if and only if

.

\rho y_{i}=\sum_{j:j\sim i}y_{j}.\qed

Recall that $\mathbf{j}$ denotes the all-ones vector.

Corollary 2.9.

$\mathbf{j}$ is an eigenvector of $A$ if and only if $G$ is regular. ∎

Fact 2.10.

If $G$ is connected and $\mathbf{y}$ is an eigenvector to eigenvalue $\lambda$ with all-positive coordinates, then $\lambda$ is the largest eigenvalue of $A$ .

Proof.

Since $\lambda_{1}$ is simple, any eigenvector $\mathbf{y}$ to an eigenvalue other than $\lambda_{1}$ must be orthogonal to the principal eigenvector. ∎

Fact 2.11.

For a connected $d$ -regular graph $G$ , $\lambda_{1}=d$ . ∎

Let $\Delta$ denote $\max_{1\leq i\leq n}\deg(i)$ , the maximum degree of $G$ .

Fact 2.12.

For every graph $G$ , we have $\lambda_{1}\leq\Delta$ . For connected graphs, equality holds if and only if $G$ is regular. ∎

We denote the quadratic mean of the degrees of vertices by

(2.2)

\deg_{\operatorname{qavg}}:=\sqrt{\frac{\sum_{i=1}^{n}\deg(i)^{2}}{n}}.

Fact 2.13.

For every graph $G$ , we have $\lambda_{1}\geq\deg_{\operatorname{qavg}}$ .

Proof.

Immediate using Rayleigh’s principle applied to $A^{2}$ and the $\mathbf{j}_{n}$ vector. ∎

2.4. Spectral gaps

For a graph $G$ , we call the quantity $\lambda_{1}(G)-\lambda_{2}(G)$ the additive spectral gap of $G$ , and the quantity $(\lambda_{1}(G)-\lambda_{2}(G))/\lambda_{1}(G)$ the multiplicative spectral gap of $G$ .

We write $L_{G}$ for the Laplacian of $G$ , defined as the $n\times n$ matrix

L_{G}=\operatorname{diag}(\deg(1),\deg(2),\dots,\deg(n))-A_{G}.

$L_{G}$ is positive semidefinite; $\mathbf{j}$ is an eigenvector of $L_{G}$ to eigenvalue zero. We write $\delta(G)$ for the smallest eigenvalue of $L_{G}$ restricted to the orthogonal complement of $\mathbf{j}$ . We note that $\delta(G)=0$ if and only if $G$ is disconnected. $\delta(G)$ is the algebraic connectivity of the graph $G$ , as first defined by Fiedler [1].

For a graph $G$ , let $f_{G}$ be the characteristic polynomial of the adjacency matrix, and $g_{G}$ the characteristic polynomial of the Laplacian. When $G$ is a $d$ -regular graph, we have

(2.3)

f_{G}(t)=g_{G}(d-t).

It follows that

(2.4)

\delta(G)=d-\lambda_{2}(G)

is the additive spectral gap of $G$ , and

(2.5)

\frac{\delta(G)}{d}=1-\frac{\lambda_{2}(G)}{d}

is the multiplicative spectral gap of $G$ . We shall discuss spectral gaps for regular graphs only.

In all notation, we omit the graph $G$ when it is clear from context.

2.5. Rates of growth

By a family of graphs, we mean an infinite set of non-isomorphic finite graphs.

Let $\mathcal{G}=\{G_{1},G_{2},\dots\}$ be a family of graphs, and let $n_{i}$ be the number of vertices of $G_{i}$ . We say $\gamma(\mathcal{G})$ is polynomially bounded if $\displaystyle{\gamma(G_{i})<n_{i}^{c}}$ for some constant $c$ and all sufficiently large $i$ . We say $\gamma(\mathcal{G})$ is exponential if $\displaystyle{\gamma(G_{i})\geq a^{n_{i}}}$ for some constant $a>1$ and all sufficiently large $i$ . We say $\gamma(\mathcal{G})$ has factorial growth if $\displaystyle{\gamma(G_{i})\geq n_{i}^{cn_{i}}}$ for some positive constant $c$ and all sufficiently large $i$ .

2.6. Subgraphs, graph products

Fact 2.14.

If $H$ is a proper subgraph of a connected graph $G$ , i.e., $H$ is obtained from $G$ by deleting at least one edge and possibly some vertices, then $\lambda_{1}(G)>\lambda_{1}(H)$ .

Proof.

Immediate using Rayleigh’s principle. ∎

Notation 2.15.

Given a graph $G$ and $U\subseteq V(G)$ , we denote the induced subgraph of $G$ on the set $U$ by $G[U]$ .

Notation 2.16.

For graphs $H=(W,F)$ and $G=(V,E)$ , the Cartesian product of $H$ and $G$ , denoted by $H\square G$ , is the graph with the set $W\times V$ as vertices, and $(w_{1},v_{1})\sim(w_{2},v_{2})$ if and only if $w_{1}=w_{2}$ and $v_{1}\sim_{G}v_{2}$ , or $v_{1}=v_{2}$ and $w_{1}\sim_{H}w_{2}$ . For each $v\in V$ , we call $(H\square G)[W\times\{v\}]$ the horizontal layer corresponding to $v$ . For each $w\in W$ , we call $(H\square G)[\{w\}\times V]$ the vertical layer corresponding to $w$ . The horizontal layers are copies of $H$ and the vertical layers are copies of $G$ .

Notation 2.17.

For graphs $H=(W,F)$ and $G=(V,E)$ , the lexicographic product of $H$ and $G$ , denoted by $H\circ G$ , is the graph with the set $W\times V$ as vertices, and $(w_{1},v_{1})\sim(w_{2},v_{2})$ if and only if either $w_{1}\sim_{H}w_{2}$ or $w_{1}=w_{2}$ and $v_{1}\sim_{G}v_{2}$ . For each $w\in W$ we call $(H\circ G)[\{w\}\times V]$ the vertical layer corresponding to $w$ .

Recall that $J_{n}$ denotes the $n\times n$ all-ones matrix.

Observation 2.18.

The adjacency matrix of $H\circ G$ is $A_{H}\otimes J_{|V(G)|}+I_{|V(H)|}\otimes A_{G}$ . ∎

3. Preliminary results about the principal eigenvector

As previously introduced, $G$ will always denote a connected graph. We write $\lambda_{1}(G)$ for the largest eigenvalue of the adjacency matrix of $G$ . We use $\mathbf{q}(G)$ to mean the principal eigenvector of the adjacency matrix, the all-positive eigenvector to $\lambda_{1}(G)$ . We assume $\mathbf{q}(G)$ is scaled to have $\ell^{2}$ norm $1$ unless otherwise stated. We write $\gamma(G)$ for the principal ratio $q_{\max}(G)/q_{\min}(G)$ of $G$ . We omit $G$ from these notations when the graph is clear from context.

3.1. Observations and naive bounds on the ratio

First, we note that $\mathbf{q}$ reflects the symmetries of $G$ .

Fact 3.1.

The principal eigenvector $\mathbf{q}$ is constant on orbits of $\operatorname{Aut}(G)$ , the automorphism group of graph $G$ . ∎

Next we note some basic bounds on the ratio between the coordinates of $\mathbf{q}$ .

Observation 3.2.

For two vertices $i,j$ in $G$ , let $\operatorname{dist}(i,j)=k$ . Then

\frac{q_{j}}{q_{i}}\leq\lambda_{1}^{k}.

Proof.

If $\operatorname{dist}(i,j)=0$ , then $q_{j}/q_{i}=1=\lambda_{1}^{0}$ . If $\operatorname{dist}(i,j)=1$ , then by Corollary 2.8 and since all $q_{w}$ are positive, $\lambda_{1}q_{i}=\sum_{w:w\sim i}q_{w}\geq q_{j}$ . Now, suppose $k\geq 2$ and $\displaystyle{q_{w}/q_{i}\leq\lambda_{1}^{k-1}}$ for all vertices $w$ at distance $k-1$ from $i$ . We know $j$ is adjacent to at least one vertex $w$ at distance $k-1$ from $i$ . Then

\frac{q_{j}}{q_{i}}=\frac{q_{j}}{q_{w}}\cdot\frac{q_{w}}{q_{1}}\leq\lambda_{1}\cdot\lambda_{1}^{k-1}=\lambda_{1}^{k}.\qed

Recall that $D$ denotes the diameter of the graph.

Corollary 3.3.

For a connected graph $G$ of diameter $D$ ,

.

\gamma\leq\lambda_{1}^{D}\leq\Delta^{D}\leq(n-1)^{D}.\qed

Corollary 3.4.

If $D$ is bounded for some family $\mathcal{G}$ of graphs , then $\gamma(\mathcal{G})$ is polynomially bounded in $n$ . ∎

Since $D$ is relevant in bounding the ratio, we introduce a bound on $D$ for regular graphs.

Fact 3.5.

Let $G$ be a connected $d$ -regular graph. Then $\displaystyle{D\leq\frac{3n}{d}}$ .

Proof.

Pick $v_{0},v_{D}$ in $G$ so that $\operatorname{dist}(v_{0},v_{D})=D$ . Let $v_{0},v_{1},\dots,v_{D}$ be a shortest path from $v_{0}$ to $v_{D}$ . Any $v_{i},v_{j}$ with $|i-j|\geq 3$ cannot have any common neighbors, since otherwise the path will not be a shortest path. Thus

d\left\lceil\frac{D}{3}\right\rceil\leq n.

Therefore $D\leq 3n/d$ . ∎

We know $D(G+e)\leq D(G)$ for any $e\in\overline{G}$ . The following result shows that $D(G+e)$ , and consequently, also $D(G-e)$ (if still connected), cannot differ from $D_{G}$ by more than a factor of $2$ .

Fact 3.6.

For a connected graph $G$ with $D(G)=D$ and $e\in E(\overline{G})$ ,

D(G+e)\geq\frac{1}{2}D(G).

Proof.

(Notation: By $\operatorname{dist}_{l}(x,y)$ , where $l$ is a path, we mean the distance between $x$ and $y$ along the path.)
We need to prove that there is a pair of vertices at distance at least $\frac{D}{2}$ in $G+e$ . Let $u,v\in V(G)$ be such that $\operatorname{dist}_{G}(u,v)=D$ . If $\operatorname{dist}_{G+e}(u,v)=D$ , we are done. Otherwise, let $p$ be a shortest path between $u$ and $v$ in $G$ , and $q$ a shortest path between $u$ and $v$ in $G+e$ . Then $e$ must be on $q$ . Denote by $x$ the endpoint of $e$ which is closer to $u$ on $q$ , and by $y$ the other endpoint. Pick the middle vertex $w$ of $p$ with $\operatorname{dist}_{p}(u,w)=\lceil\frac{D}{2}\rceil$ . If $\operatorname{dist}_{G+e}(u,w)=\operatorname{dist}_{G}(u,w)=\lceil\frac{D}{2}\rceil$ , we are done. Otherwise, any shortest path $r$ in $G+e$ from $u$ to $w$ must pass through edge $e$ . Suppose we go along $r$ from $u$ to $w$ . By the optimality of $q$ , we may assume that $r$ and $q$ overlap from $u$ to $y$ . Now we look at the vertex $w^{\prime}$ adjacent to $w$ on $p$ which is closer to $u$ than to $v$ . We have

(3.1)

\operatorname{dist}_{G}(w^{\prime},v)=\operatorname{dist}_{p}(w^{\prime},v)=\left\lfloor\frac{D}{2}\right\rfloor+1.

We claim that there is a shortest path in $G+e$ from $w^{\prime}$ to $v$ that does not pass through $e$ . Let $s$ be a shortest path in $G+e$ from $w^{\prime}$ to $v$ that passes through $e$ . By the optimality of $q$ , we may assume that $s$ and $q$ overlap from $x$ to $v$ . Then by the optimality of $r$ ,

\operatorname{dist}_{s}(x,w^{\prime})+\operatorname{dist}_{G+e}(w^{\prime},w)\geq\operatorname{dist}_{r}(x,w)=\operatorname{dist}_{G+e}(x,y)+\operatorname{dist}_{r}(y,w),

that is,

\operatorname{dist}_{s}(x,w^{\prime})\geq\operatorname{dist}_{r}(y,w).

Therefore

\operatorname{dist}_{s}(w^{\prime},y)=\operatorname{dist}_{s}(w^{\prime},x)+\operatorname{dist}_{G+e}(x,y)\geq\operatorname{dist}_{G+e}(w^{\prime},w)+\operatorname{dist}_{r}(w,y).

Thus $s$ is equivalent to a path that does not pass through $e$ in $G+e$ . As a result, a shortest path between $w^{\prime}$ and $v$ in $G+e$ is also available in $G$ . Then by (3.1),

\operatorname{dist}_{G+e}(w^{\prime},v)=\operatorname{dist}_{G}(w^{\prime},v)=\left\lfloor\frac{D}{2}\right\rfloor+1.\qed

3.2. Chebyshev polynomials and principal eigenvectors

The Chebyshev polynomials of the first kind, $T_{n}$ , can be characterized by the recurrence

(3.2)

T_{n+1}(t)=2t\cdot T_{n}(t)-T_{n-1}(t),

with initial values $T_{0}(t)=1$ and $T_{1}(t)=t$ .
The Chebyshev polynomials of the second kind, $U_{n}$ , can be characterized by the same recurrence

(3.3)

U_{n+1}(t)=2t\cdot U_{n}(t)-U_{n-1}(t),

with initial values $U_{0}(t)=1$ and $U_{1}(t)=2t$ .

Fact 3.7.

When $|t|\geq 1$ , the explicit formula for $T_{n}$ is

(3.4)

T_{n}(t)=\frac{1}{2}\Big{(}\Big{(}t-\sqrt{t^{2}-1}\Big{)}^{n}+\Big{(}t+\sqrt{t^{2}-1}\Big{)}^{n}\Big{)}.

and the explicit formula for $U_{n}$ is

Proof.

(3.5)

U_{n}(t)=\frac{\Big{(}t+\sqrt{t^{2}-1}\Big{)}^{n+1}-\Big{(}t-\sqrt{t^{2}-1}\Big{)}^{n+1}}{2\sqrt{t^{2}-1}}.\qed

Fact 3.8.

When $x>1$ , both $T_{n}(x)$ and $U_{n}(x)$ are strictly increasing. ∎

Definition 3.9.

A pendant path of length $k$ in $G$ consists of $k$ vertices such that the induced subgraph on them is a path; moreover, one vertex has degree $1$ in $G$ and $k-2$ vertices have degree $2$ in $G$ . For example, in the graph $P_{r}\cdot K_{s}$ , there is a pendant path of length $r$ .

Observation 3.10.

Let $1,2,\dots,k$ be a pendant path in $G$ where consecutive vertices are adjacent and $\deg(1)=1$ . Then for $1\leq j\leq k$ ,

\frac{q_{j}}{q_{1}}=U_{j-1}\left(\frac{\lambda_{1}}{2}\right).

Proof.

By Corollary 2.8, $\lambda_{1}q_{1}=q_{2}$ and $q_{j+1}=\lambda_{1}q_{j}-q_{j-1}$ for $1\leq j\leq n-1$ . Therefore $q_{j}/q_{1}$ satisfies the initial values and recurrence relation of $U_{j-1}(\lambda_{1}/2)$ . ∎

In fact, this occurence was observed by Tait and Tobin [8] when they proved that the maximum principal ratio over all graphs of $n$ vertices is attained by a kite graph.

4. Stability of the ratio: adding or removing edges in bounded distance

In this section and the subsequent sections, we are interested in the stability of the ratio with respect to a small change in the graph.

Let $G$ be a $d$ -regular graph, so $\gamma(G)=1$ . As introduced before, we use $G+e$ to denote the graph obtained by adding an edge $e\in E(\overline{G})$ to $G$ , and $G-e$ to denote the graph obtained by deleting an edge $e\in E(G)$ from $G$ . We always assume $G-e$ is still connected. We are interested in the possible asymptotic behaviors of $\gamma(G+e)$ and $\gamma(G-e)$ .

We first make two simple observations. For the first one, we do not require $G$ to be regular.

Observation 4.1.

If the diameter $D(G)$ is bounded, then $\gamma(G\pm e)$ is polynomially bounded in $n$ .

Proof.

Fact 3.6 shows that $D(G\pm e)$ is also bounded, and the statement follows from Cororllary 3.4. ∎

Observation 4.2.

Let $G$ be a $d$ -regular graph. If $d$ is linear in $n$ , i.e., $d/n$ is bounded away from $0$ , then $\gamma(G\pm e)$ is polynomially bounded in $n$ .

Proof.

Fact 3.5 shows that $D(G)$ is bounded, and the statement follows from Observation 4.1. ∎

4.1. Adding an edge

We show that if we add an edge $e$ between two vertices at distance $2$ to a connected regular graph $G$ of bounded degree, then $\gamma(G+e)$ can be exponentially large.

Theorem 4.3.

For any $d\geq 2$ and $n>18d^{3}$ such that $n/(d-1)$ is an odd integer, there exists a $d$ -regular graph $G_{n,d}$ with $n$ vertices and an edge $e_{n,d}\in E(\overline{G_{n,d}})$ between two vertices at distance 2 in $G_{n,d}$ , such that

(4.1)

\gamma(G_{n,d}+e_{n,d})>\mathrm{e}^{n/(18d^{3})}.

In particular, when $d$ is bounded, $\gamma(G_{n,d}+e_{n,d})$ is exponential in $n$ .

The proof of this theorem will be based on a series of constructions. The graphs produced by Construction 4.6 and Construction 4.7 are the pair of graphs that are used in the proof.

Construction 4.4 ( $\operatorname{Ring}_{r,d,G_{2}}$ ).

Let $r\geq 0$ be a parameter. We label the vertices in $P_{2r+1}$ from one end to the other end as $p_{-r}$ , $p_{-r+1}$ , …, $p_{-1}$ , $p_{0}$ , $p_{1}$ , …, $p_{r-1}$ , $p_{r}$ . Let $\displaystyle{G_{1}=P_{2r+1}\square K_{d-1}}$ . We label the vertical layer corresponding to $p_{i}$ as $L_{i}$ . Let $G_{2}$ , which we will call a “gadget,” be a connected graph with two vertices $v_{1}$ , $v_{2}$ of degree $1$ and all other vertices of degree $d$ , and an automorphism that switches $v_{1}$ and $v_{2}$ . We connect $v_{1}$ with every vertex in $L_{-r}$ and connect $v_{2}$ with every vertex in $L_{r}$ . We call the graph obtained $\operatorname{Ring}_{r,d,G_{2}}$ .

Observation 4.5.

Let $X\leq\operatorname{Aut}(G_{1})$ be the subgroup of automorphisms of $G_{1}$ that fixes the vertical layers and permutes the horizontal layers. The orbits of $X$ are the vertical layers. $X$ is isomorphic to the symmetric group $S_{d-1}$ . This group extends to $G$ . The automorphism of $G_{1}$ that switches $L_{j}$ and $L_{-j}$ for $0\leq j\leq r$ also extends to $G$ . Therefore the coordinates of the principal eigenvector of $\operatorname{Ring}_{r,d,G_{2}}$ corresponding to all vertices in $L_{j}\cup L_{-j}$ are the same. We denote this value by $a_{j}$ , for $0\leq j\leq r$ .

Construction 4.6.

[ $\operatorname{Ring}_{r,d}$ ] Now we specify the gadget $G_{2}$ . We take two copies of $K_{d+1}$ and call them $H_{1}$ , $H_{2}$ . We label the vertices in $H_{1}$ , $H_{2}$ from $1$ to $d+1$ . We remove the edge $\{1,2\}$ from $H_{2}$ , the edge $\{3,4\}$ from $H_{1}$ , and add the edges $\{1,3\}$ and $\{2,4\}$ . We find two vertices $u_{1}$ , $u_{2}$ in $V(H_{1})$ such that $u_{2}\in\mathcal{O}(u_{1})$ in $H_{1}-\{3,4\}$ . We remove the edge $\{u_{1},u_{2}\}$ . Finally, we attach a dangling vertex $w_{1}$ to $u_{1}$ , and a dangling vertex $w_{2}$ to $u_{2}$ . $w_{1}$ and $w_{2}$ are the vertices that connect with $L_{-r}$ and $L_{r}$ , respectively. For this specific $G_{2}$ , $\operatorname{Ring}(r,d,G_{2})$ is a $d$ -regular graph on $n=(2r+1)(d-1)+2+2(d+1)=2rd-2r+3d+3$ vertices. We write $\operatorname{Ring}(r,d)$ for this graph.

Construction 4.7.

[ $\operatorname{Ring}_{r,d}+e$ ] We add the edge $e=\{3,4\}\in E(\overline{\operatorname{Ring}_{r,d}})$ to $\operatorname{Ring}_{r,d}$ .

Proposition 4.8.

For $0\leq j\leq r$ ,

\frac{a_{j}}{a_{0}}=T_{j}\left(\frac{\lambda_{1}(\operatorname{Ring}_{r,d}+e)-d+2}{2}\right)

where $a_{j}$ is as defined in Observation 4.5.

Proof.

By Corollary 2.8,

\lambda_{1}a_{0}=(d-2)a_{0}+2a_{1}

and

\lambda_{1}a_{j}=(d-2)a_{j}+a_{j-1}+a_{j+1}

for $1\leq j\leq n-1$ . Therefore $a_{j}/a_{0}$ satisfies the initial values and recurrence relation of $T_{j}((\lambda_{1}-d+2)/2)$ according to (3.2). ∎

Lemma 4.9.

$\lambda_{1}(\operatorname{Ring}_{r,d}+e)>d+c(d)$ , where $c(d):=2/(3d(d+1))$ .

Proof.

Let $H$ be the induced subgraph of $\operatorname{Ring}_{r,d}$ on $V(H_{1})\cup V(H_{2})$ . Then

\deg_{H+e}(1)=\deg_{H+e}(2)=d+1,\quad\deg_{H+e}(u_{1})=\deg_{H+e}(u_{2})=d-1,

while the rest of the vertices in $H+e$ are of degree $d$ . Then by Fact 2.14 and Fact 2.13,

\lambda_{1}(\operatorname{Ring}_{r,d}+e)>\lambda_{1}(H+e)\geq\deg_{\operatorname{qavg}}(H+e)=\sqrt{\frac{(2d+2)d^{2}+4}{2d+2}}=d\sqrt{1+\frac{2}{d^{2}(d+1)}}.

Since $\displaystyle{\sqrt{1+x}>1+\frac{1}{3}x}$ when $0<x<3$ , we have $\displaystyle{\lambda_{1}(G+e)>d+c(d)}$ , as claimed. ∎

Proof of Theorem 4.3.

By Lemma 4.9,

\frac{\lambda_{1}(\operatorname{Ring}_{r,d}+e)-d+2}{2}>1+\frac{1}{3d(d+1)}.

By Proposition 4.8, Fact 3.8, and Fact 3.7,

\gamma(\operatorname{Ring}_{r,d})\geq\frac{a_{r}}{a_{0}}=T_{r}\left(\frac{\lambda_{1}(\operatorname{Ring}_{r,d}+e)-d+2}{2}\right)>T_{j}\left(1+\frac{1}{3d(d+1)}\right)>\frac{1}{2}\left(1+\frac{1}{3d(d+1)}\right)^{r}.

Plugging in $\displaystyle{r=\frac{n-3d-3}{2d-2}}$ and assuming $n>18d^{3}$ , we infer by a simple calculation that

\gamma(\operatorname{Ring}_{r,d})>\mathrm{e}^{n/(18d^{3})}.\qed

4.2. Removing an edge

Let $e=\{1,2\}$ .

We show that in the case of removing the edge $e$ when $\operatorname{dist}_{G-e}(1,2)$ is bounded, $\gamma(G-e)$ is polynomially bounded for all $D$ . We make use of the following theorem.

Theorem 4.10 (Cioabă, Gregory, Nikiforov[7]).

If $G$ is a connected nonregular graph with $n$ vertices, diameter $D$ , and maximum degree $\Delta$ , then

\Delta-\lambda_{1}(G)\geq\frac{1}{n(D+1)}.

Theorem 4.11.

For a connected $d$ -regular graph $G$ and an edge $e=\{1,2\}\in E(G)$ , if $\operatorname{dist}_{G-e}(1,2)<c$ where $c$ is some constant, then $\gamma(G-e)$ is polynomially bounded in $n$ .

Lemma 4.12.

$q_{\min}(G-e)$ is either $q_{1}$ or $q_{2}$ .

Proof.

If $q_{\min}$ corresponds to some vertex $j$ with degree $d$ , then the average of the coordinates corresponding to the neighbors of $j$ would be

\frac{\lambda_{1}(G-e)q_{j}}{d}<\frac{\lambda_{1}(G-e)q_{j}}{\lambda_{1}(G-e)}=q_{j},

which is a contradiction. ∎

Proof of Theorem 4.11.

Without loss of generality suppose $q_{1}=q_{\min}$ . Then summing $n$ equations of the form $\lambda_{1}(G-e)q_{i}=\sum_{j:j\sim i}q_{j}$ , we have

\lambda_{1}(G-e)\sum_{i=1}^{n}q_{i}=(d-1)q_{1}+(d-1)q_{2}+dq_{3}+\cdots+dq_{n}=d\left(\sum_{i=1}^{n}q_{i}\right)-q_{1}-q_{2}.

Therefore by Theorem 4.10,

\frac{q_{1}+q_{2}}{\sum_{i=1}^{n}q_{i}}=d-\lambda_{1}(G-e)\geq\frac{1}{n(D(G-e)+1)}\geq\frac{1}{n^{2}}.

By Observation 3.2, $q_{2}\leq\lambda_{1}(G-e)^{c}q_{1}$ . Therefore

\gamma(G-e)<\frac{\sum_{i=1}^{n}q_{i}}{q_{1}}\leq n^{2}\left(1+\frac{q_{2}}{q_{1}}\right)\leq n^{2}(1+\lambda_{1}(G-e)^{c})<n^{2}(1+d^{c}).\qed

5. Stability of the ratio: multiplicative spectral gap

We use a known bound on the diameter of a graph in terms of the spectral gap to show that $\gamma(G\pm e)$ is polynomially bounded for bounded-degree expanders.

Definition 5.1.

For $0<\epsilon<1$ , a regular graph of degree $d$ is an $\epsilon$ -expander if $\displaystyle{\lambda_{2}\leq(1-\epsilon)d}$ , i.e., $\displaystyle{\delta\geq\epsilon d}$ .

We note that this definition implies that an expander graph is connected.

Theorem 5.2 (N. Alon, V. D. Milman[2]).

Let $G$ be a connected graph on $n$ vertices with maximum degree $\Delta$ and let $\delta$ denote the smallest positive eigenvalue of the Laplacian matrix. Then

D(G)\leq 2\left\lfloor\sqrt{\frac{2\Delta}{\delta}}\log_{2}n\right\rfloor.

Corollary 5.3.

For $d$ -regular $\epsilon$ -expander graphs $G$ , we have

(5.1)

\gamma(G+e)\leq n^{4\sqrt{2/\epsilon}\log_{2}(d+1)}.

In particcular, for expander graphs $G$ with bounded degree, $\gamma(G\pm e)$ is polynomially bounded in $n$ .

Proof.

By definition,

\frac{\Delta(G)}{\delta(G)}=\frac{d}{\delta(G)}\leq\frac{1}{\epsilon}.

Then

D(G)\leq 2\left\lfloor\sqrt{\frac{2}{\epsilon}}\log_{2}n\right\rfloor.

By Fact 3.6,

D(G\pm e)\leq 4\left\lfloor\sqrt{\frac{2}{\epsilon}}\log_{2}n\right\rfloor.

Since $\gamma\leq\Delta^{D}$ (Corollary 3.3),

	$\displaystyle\gamma(G\pm e)$	$\displaystyle\leq(d+1)^{4\left\lfloor\sqrt{2/\epsilon}\log_{2}n\right\rfloor}$
		$\displaystyle\leq(d+1)^{4\sqrt{2/\epsilon}\log_{2}n}$
		$\displaystyle=2^{4\sqrt{2/\epsilon}\log_{2}n\log_{2}(d+1)}$
		$\displaystyle=n^{4\sqrt{2/\epsilon}\log_{2}(d+1)}.\qed$

6. Stability of the ratio: additive spectral gap

We show that a large ( $(2+\epsilon)\sqrt{n}$ ) additive spectral gap implies that $\gamma(G\pm e)$ is bounded. Specifically, we prove the following.

Theorem 6.1.

Let $G$ be a connected $d$ -regular graph. If the additive spectral gap $\delta=d-\lambda_{2}$ of $G$ satisfies $\displaystyle{\delta>\frac{2}{c}\sqrt{n}}+2$ for some value $0<c<1$ , then

\gamma(G\pm e)<\frac{1+c}{1-c}.

To motivate this result, we first point out that graphs with such an additive spectral gap are not necessarily expanders. Indeed, when $d$ is greater than $\Theta(\sqrt{n})$ , the multiplicative spectral gap of graphs with a $\Theta(\sqrt{n})$ additive spectral graph will go to zero. Moreover, the diameter of graphs with such an additive spectral gap can still grow quite fast (polynomially in $n$ ), approaching the upper bound derived from Theorem 5.2.

6.1. Existence of graphs with large additive spectral gap and large diameter

Proposition 6.2.

For a regular graph with additive spectral gap $\delta$ , the diameter $D$ is $O((n/\delta)^{1/3}(\log n)^{2/3})$ .

Proof.

Let the regular graph have degree $d$ . From Theorem 5.2, we know that

(6.1)

D^{2}\leq c\frac{d}{\delta}(\log n)^{2}

where $c$ is some constant. By Fact 3.5, we also have

(6.2)

D\leq\frac{3n}{d}.

Multiplying (6.1) and (6.2), we have

(6.3)

D\leq(3c)^{1/3}\left(\frac{n}{\delta}\right)^{1/3}(\log n)^{2/3}.\qed

Corollary 6.3.

For a regular graph with an $\Omega(\sqrt{n})$ additive spectral gap, the diameter is $O(n^{1/6}(\log n)^{2/3})$ .

We show that this bound is nearly tight.

Proposition 6.4.

There are connected regular graphs with diameter $(1/2)n^{1/6}$ and an additive spectral gap of $cn^{1/2}$ where $c=2\pi^{2}(1+O(n^{-1/3}))$ .

We prove a more general statement.

Proposition 6.5.

For any constant $0<t<1$ , there are connected regular graphs with diameter $(1/2)n^{(1-t)/3}$ and an additive spectral gap of $cn^{t}$ where
$c=2\pi^{2}(1+O(n^{(2t-2)/3}))$ .

Proof.

Recall the lexicographic product and its properties in Definition 2.17, Observation 2.18, and Fact 2.5. Let $G:=C_{r}\circ\overline{K}_{s}$ where $r\cdot s=n$ . Then $G$ is a connected regular graph of degree $2s$ and diameter $\lfloor r/2\rfloor$ . The adjacency matrix of $G$ can be expressed as

(6.4)

A_{G}=A_{C_{r}}\otimes J_{s}+I_{r}\otimes\mathbf{0}=A_{C_{r}}\otimes J_{s}.

Since

(6.5)

\operatorname{spec}(J_{s})=\{\{s,0^{s-1}\}\},

we have

(6.6)

\operatorname{spec}(G)=\{\{s\lambda_{1}(C_{r}),s\lambda_{2}(C_{r}),\dots,s\lambda_{r}(C_{r}),0^{(s-1)r}.\}\}

Thus

\delta(G)=s(\lambda_{1}(C_{r})-\lambda_{2}(C_{r})).

By Fact 2.3,

\lambda_{1}(C_{r})-\lambda_{2}(C_{r})=2\left(1-\cos\left(\frac{2\pi}{r}\right)\right)=\frac{4\pi^{2}}{r^{2}}+\epsilon

where $\displaystyle{|\epsilon|<\frac{2^{5}\pi^{4}}{4!r^{4}}}$ . We take $\displaystyle{r=n^{(1-t)/3}}$ and $\displaystyle{s=n^{(2+t)/3}}$ . Then

\delta(G)=4\pi^{2}n^{t}\left(1+O\left(\frac{1}{r^{2}}\right)\right)=4\pi^{2}n^{t}\left(1+O(n^{(2t-2)/3})\right).\qed

6.2. Large additive spectral gap implies bounded ratio

Now we prove Theorem 6.1 which shows that $\gamma(G\pm e)$ is bounded when $G$ has an additive spectral gap of $(2+\epsilon)\sqrt{n}$ for some $\epsilon>0$ . The proof is an adaptation of the theory developed in Chapter V. 2 in Stewart and Sun’s book [3], dealing with perturbation of invariant subspaces. In addition to adapting the proofs to our special case, we fill in some details to make the proof accessible to readers not versed in perturbation theory.

Notation 6.6.

Let $U\in M_{n}(\mathbb{R})$ be the orthogonal matrix whose columns are eigenvectors of $A$ . We can write it as

(6.7)

U=(\mathbf{x}\;Y)=(\mathbf{x}\;\mathbf{y}_{2}\;\cdots\;\mathbf{y}_{n}),

where the columns $\mathbf{x},\mathbf{y}_{2},\mathbf{y}_{3},\dots,\mathbf{y}_{n}$ are eigenvectors of $A$ corresponding to eigenvalues $\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}\geq\dots\geq\lambda_{n}$ . Then $\lambda_{1}=d$ , and we can assume

(6.8)

\mathbf{x}=\left(\frac{1}{\sqrt{n}},\dots,\frac{1}{\sqrt{n}}\right)^{T}.

In the context of adding an edge $e$ to $G$ , we label the two endpoints of $e$ to be $1$ and $2$ , and let $E\in M_{n}(\mathbb{R})$ have $E_{21}=E_{12}=1$ while all other coordinates are zero. In the context of deleting an edge $e$ from $G$ , we also label the two endpoints of $e$ to be $1$ and $2$ , and let $E\in M_{n}(\mathbb{R})$ have $E_{21}=E_{12}=-1$ while all other coordinates are zero. In both cases, $A+E$ is the adjacency matrix of the graph obtained.

6.2.1. Rotating the eigenbasis

We know $\mathbf{x}$ is not an eigenvector of $A+E$ . We want to know how close $\mathbf{x}$ is to the principal eigenvector of $G\pm e$ , in the sense that we want to find a vector $\mathbf{v}$ with small norm such that $\displaystyle{\widetilde{\mathbf{x}}=\frac{\mathbf{x}+\mathbf{v}}{\|\mathbf{x}+\mathbf{v}\|}}$ is the unit principal eigenvector of $G\pm e$ .

Proposition 6.7.

Let $\mathbf{p}$ be a vector in $\mathbb{R}^{n-1}$ . Let $U=(\mathbf{x}\;Y)\in M_{n}(\mathbb{R})$ be orthogonal, where $\mathbf{x}$ is a vector in $\mathbb{R}^{n-1}$ and $Y$ is an $n\times(n-1)$ matrix. Define $\widetilde{U}\in M_{n}(\mathbb{R})$ as $\displaystyle{\widetilde{U}=(\widetilde{\mathbf{x}}\;\widetilde{Y})}$ , where

(6.9)

\widetilde{\mathbf{x}}=\frac{\mathbf{x}+Y\mathbf{p}}{\sqrt{1+\|\mathbf{p}\|^{2}}}\quad\text{and}\quad\widetilde{Y}=(Y-\mathbf{x}\mathbf{p}^{T})(I_{n-1}+\mathbf{p}\mathbf{p}^{T})^{-1/2}.

Then $\widetilde{U}$ is an orthogonal matrix.

Proof.

\widetilde{\mathbf{x}}^{T}\widetilde{\mathbf{x}}=\frac{\mathbf{x}^{T}\mathbf{x}+\mathbf{p}^{T}Y^{T}Y\mathbf{p}}{1+\|\mathbf{p}\|^{2}}=\frac{1+\|\mathbf{p}\|^{2}}{1+\|\mathbf{p}\|^{2}}=1.

	$\displaystyle\widetilde{Y}^{T}\widetilde{Y}$	$\displaystyle=(I_{n-1}+\mathbf{p}\mathbf{p}^{T})^{-1/2}(Y^{T}-\mathbf{p}\mathbf{x}^{T})(Y-\mathbf{x}\mathbf{p}^{T})(I_{n-1}+\mathbf{p}\mathbf{p}^{T})^{-1/2}$
		$\displaystyle=(I_{n-1}+\mathbf{p}\mathbf{p}^{T})^{-1/2}(I_{n-1}+\mathbf{p}\mathbf{p}^{T})(I_{n-1}+\mathbf{p}\mathbf{p}^{T})^{-1/2}$
		$\displaystyle=I_{n-1}.$

	$\displaystyle\widetilde{\mathbf{x}}^{T}\widetilde{Y}$	$\displaystyle=\frac{(\mathbf{x}^{T}+\mathbf{p}^{T}Y^{T})(Y-\mathbf{x}\mathbf{p}^{T})(I_{n-1}+\mathbf{p}\mathbf{p}^{T})^{-1/2}}{\sqrt{1+\\|\mathbf{p}\\|^{2}}}$
		$\displaystyle=\frac{(-\mathbf{p}^{T}+\mathbf{p}^{T})(I_{n-1}+\mathbf{p}\mathbf{p}^{T})^{-1/2}}{\sqrt{1+\\|\mathbf{p}\\|^{2}}}$
		$\displaystyle=0.$

Therefore

\widetilde{U}^{T}\widetilde{U}=\begin{pmatrix}\widetilde{\mathbf{x}}^{T}\widetilde{\mathbf{x}}&\widetilde{\mathbf{x}}^{T}\widetilde{Y}\\ \widetilde{Y}^{T}\widetilde{\mathbf{x}}&\widetilde{Y}^{T}\widetilde{Y}\end{pmatrix}=I_{n}.\qed

6.2.2. Rotating $\mathbf{x}$ to be an eigenvector

We want to find $\mathbf{p}$ such that $\widetilde{\mathbf{x}}$ is the principal eigenvector of $A+E$ .

Notation 6.8.

We define

e_{11}:=\mathbf{x}^{T}E\mathbf{x}\in\mathbb{R},\quad e_{21}:=Y^{T}E\mathbf{x}\in\mathbb{R}^{n-1},\quad E_{22}:=Y^{T}EY\in M_{n-1}(\mathbb{R}),

\text{and}\quad L:=Y^{T}AY=\operatorname{diag}(\lambda_{2},\dots,\lambda_{n})\in M_{n-1}(\mathbb{R}).

Observation 6.9.

Since $\|E\|=1$ and $(\mathbf{x}\>Y)$ is orthogonal, $\displaystyle{|e_{11}|,\|e_{21}\|,\|E_{22}\|\leq 1}$ .

Proposition 6.10.

(6.10)

((d+e_{11})I_{n-1}-(L+E_{22}))\mathbf{p}=e_{21}-\mathbf{p}e_{21}^{T}\mathbf{p},

then $\widetilde{\mathbf{x}}$ is an eigenvector of $A+E$ .

Proof.

(6.10) is equivalent to

(Y^{T}-\mathbf{p}\mathbf{x}^{T})(A+E)(\mathbf{x}+Y\mathbf{p})=0,

which gives

\widetilde{Y}^{T}(A+E)\widetilde{\mathbf{x}}=0.

Since $(\widetilde{\mathbf{x}}\;\widetilde{Y})$ is an orthogonal matrix, $\widetilde{\mathbf{x}}$ is an eigenvector of $A+E$ . ∎

6.2.3. Finding small $\mathbf{p}$ when the additive spectral gap is large

Notation 6.11.

We define $M\in M_{n-1}(\mathbb{R})$ as $M=(d+e_{11})I_{n-1}-L-E_{22}$ .

Proposition 6.12.

If $\displaystyle{\delta>\frac{2}{c}\sqrt{n}+2}$ for some value $0<c<1$ , then $M$ is non-singular and

(6.11)

\|M^{-1}\|\leq\frac{1}{\delta-2}<\frac{c}{2\sqrt{n}}.

Proof.

Since $(d+e_{11})I_{n-1}-L$ is a diagonal matrix and $E_{22}$ is a symmetric matrix, $M$ is symmetrix. Recall that $\|E_{22}\|\leq 1$ . By Rayleigh’s principle and Observation 6.9,

	$\displaystyle\min\operatorname{spec}(M)$	$\displaystyle=\min_{\\|\mathbf{x}\\|=1}\mathbf{x}^{T}((d+e_{11})I_{n-1}-L-E_{22})\mathbf{x}$
		$\displaystyle\geq\min_{\\|\mathbf{x}\\|=1}\mathbf{x}^{T}((d+e_{11})I_{n-1}-L)\mathbf{x}-1$
		$\displaystyle=\min_{\\|\mathbf{x}\\|=1}\operatorname{spec}((d+e_{11})I-L)-1$
		$\displaystyle=d+e_{11}-\lambda_{2}-1$
		$\displaystyle\geq\delta-2.$

Therefore all eigenvalues of $M$ are positive, and

\|M^{-1}\|=\max\operatorname{spec}(M^{-1})=\frac{1}{\min\;\operatorname{spec}(M)}\leq\frac{1}{\delta-2}<\frac{c}{2\sqrt{n}}.\qed

Proposition 6.13.

We write (6.10) in terms of $M$ :

(6.12)

M\mathbf{p}=e_{21}-\mathbf{p}e_{21}^{T}\mathbf{p}.

Let $\theta=\|M^{-1}\|^{-1}$ and $\eta=\|e_{21}\|$ . We claim that if $\delta>\frac{2}{c}\sqrt{n}+2$ for some value $0<c<1$ , then there exists $\mathbf{p}$ with

(6.13)

\|\mathbf{p}\|<\frac{2\eta}{\theta+\sqrt{\theta^{2}-4\eta^{2}}}

such that (6.12) holds, and thus $\widetilde{\mathbf{x}}$ defined by (6.9) is an eigenvector of $A+E$ .

Proof.

We want to find a solution with small norm to the non-linear equation (6.12). We do this by an iterative construction.

We define a sequence of vectors $\mathbf{p}_{0},\mathbf{p}_{1},\dots$ such that

\mathbf{p}_{0}=0\quad\text{and}\quad\mathbf{p}_{i}=M^{-1}(e_{21}-\mathbf{p}_{i-1}e_{21}^{T}\mathbf{p}_{i-1}),\quad\text{for}\quad i\geq 1.

Then

\|\mathbf{p}_{i}\|\leq\|M^{-1}\|(|e_{21}|+\|\mathbf{p}_{i-1}\|^{2}|e_{21}|)\leq\frac{\eta(1+\|\mathbf{p}_{i-1}\|^{2})}{\theta}.

We claim that the sequence $\{\mathbf{p}_{i}\}$ converges. We define

\xi_{0}=0,\quad\xi_{i}=\frac{\eta(1+\xi_{i-1}^{2})}{\theta},\quad\text{for}\quad i\geq 1.

Then $\|\mathbf{p}_{i}\|\leq\xi_{i}$ . Since $\xi_{1}=\frac{\eta}{\theta}>\xi_{0}$ , we can prove by induction that $\xi_{0},\xi_{1},\xi_{2},\dots$ is monotone increasing. Let

\phi(\xi)=\frac{\eta(1+\xi^{2})}{\theta}.

This function is monotone increasing in $\xi$ , and has a fixed point at $\displaystyle{\xi=\frac{2\eta}{\theta+\sqrt{\theta^{2}-4\eta^{2}}}}$ . Then $\xi_{i}<\xi_{i+1}=\phi(\xi_{i})<\phi(\xi)=\xi$ . Therefore the sequence $\{\xi_{i}\}$ converges to $\xi$ . Thus

\|\mathbf{p}_{i}\|\leq\xi_{i}\leq\xi=\frac{2\eta}{\theta+\sqrt{\theta^{2}-4\eta^{2}}}<\frac{2\eta}{\theta}.

Next we prove the convergence of $\{\mathbf{p}_{0},\mathbf{p}_{1},\dots\}$ . For any $i\geq 2$ ,

	$\displaystyle\\|\mathbf{p}_{i}-\mathbf{p}_{i-1}\\|$	$\displaystyle=\|M^{-1}(\mathbf{p}_{i-1}e_{21}^{T}\mathbf{p}_{i-1}-\mathbf{p}_{i-2}e_{21}^{T}\mathbf{p}_{i-2})$
		$\displaystyle=\|M^{-1}(\mathbf{p}_{i-1}+\mathbf{p}_{i-2})e_{21}^{T}(\mathbf{p}_{i-1}-\mathbf{p}_{i-2})\|$
		$\displaystyle\leq 2\\|M^{-1}\\|\\|\mathbf{p}_{i-1}\\|\\|\mathbf{p}_{i-1}\\|\cdot\eta\cdot\\|\mathbf{p}_{i-1}-\mathbf{p}_{i-2}\\|$
		$\displaystyle\leq\frac{4\eta^{2}}{\theta^{2}}\\|\mathbf{p}_{i-1}-\mathbf{p}_{i-2}\\|.$

Then $\|\mathbf{p}_{i}-\mathbf{p}_{0}\|\leq\rho^{i}\|\mathbf{p}_{1}-\mathbf{p}_{0}\|$ , where $\rho=\displaystyle{\frac{4\eta^{2}}{\theta^{2}}}<\frac{c^{2}}{4n}<1$ . Therefore $\{\mathbf{p}_{i}\}$ is a Cauchy sequence in $\mathbb{R}^{n-1}$ and has a limit $\mathbf{p}$ . Thus a solution $\mathbf{p}$ exists, with norm satisfying (6.13).

∎

6.2.4. Using the bound on $\|\mathbf{p}\|$ to show that $\tilde{\mathbf{x}}$ is the principal eigenvector

Proposition 6.14.

If $\delta>\frac{2}{c}\sqrt{n}+2$ for some value $0<c<1$ , then the principal eigenvector $\widetilde{\mathbf{x}}$ of $A+E$ can be writen in the form

\widetilde{\mathbf{x}}=\frac{\mathbf{x}+Y\mathbf{p}}{\sqrt{1+\|\mathbf{p}\|^{2}}}\quad\text{where}\quad\|\mathbf{p}\|<\frac{c}{\sqrt{n}}.

Proof.

We showed that there exists $\mathbf{p}$ with

\|\mathbf{p}\|<\frac{2\eta}{\theta+\sqrt{\theta^{2}-4\eta^{2}}}<\frac{2\eta}{\theta}<\frac{c}{\sqrt{n}}

such that $\displaystyle{\frac{\mathbf{x}+Y\mathbf{p}}{\sqrt{1+\|\mathbf{p}\|^{2}}}}$ is an eigenvector of $A+E$ . It remains to show that this is the principal eigenvector. Since $\|Y\|=1$ and $\|\mathbf{p}\|<\displaystyle{\frac{c}{\sqrt{n}}}$ where $0<c<1$ , and since $\mathbf{x}=\displaystyle{\left(\frac{1}{\sqrt{n}},\dots,\frac{1}{\sqrt{n}}\right)}$ , all coordinates of $\widetilde{\mathbf{x}}$ are positive. Therefore by Fact 2.10, $\widetilde{\mathbf{x}}$ is the principal eigenvector of $A+E$ . ∎

6.2.5. Completing the proof of Theorem 6.1

Following the argument above, we know the smallest possible coordinate of $\widetilde{\mathbf{x}}$ is $\displaystyle{\frac{1-c}{\sqrt{n}}}$ , and the largest possible coordinate of $\widetilde{\mathbf{x}}$ is $\displaystyle{\frac{1+c}{\sqrt{n}}}$ . Therefore the ratio of $G\pm e$ is as claimed. This completes the proof. ∎

7. Open questions

In Section 4.2, we showed that if we remove a non-bridge edge $e$ from a connected regular graph such that the endpoints of $e$ are of bounded distance in $G-e$ , then $\gamma(G-e)$ is polynomially bounded. Is there also a polynomial bound when the endpoints of $e$ are of unbounded distance in $G-e$ ?

Question 7.1.

If we remove a non-bridge edge $e$ from a connected regular graph $G$ , is $\gamma(G-e)$ always polynomially bounded?

In Section 4.1, we showed that if we add an edge $e$ between two vertices at distance $2$ to a connected regular graph $G$ of bounded degree, then $\gamma(G+e)$ can be exponential. Can $\gamma(G+e)$ be exponential when $e$ is between two vertices of unbounded distance in $G$ ?

Question 7.2.

If we add an edge $e$ to a connected regular graph $G$ with bounded degree $d$ , such that the disance between the endpoints of $e$ in $G$ is unbouneded, can $\gamma(G+e)$ be exponential in $n$ ?

In Section 6.2, we showed that for a connected regular graph $G$ , an additive spectral gap greater than $2\sqrt{n}$ implies that $\gamma(G\pm e)$ is bounded (Theorem 6.1). However, this bound ceases to work at all for $G$ with an additive spectral gap $\delta\leq 2\sqrt{n}$ . Is this a limitaton of the method, or is there really an abrupt change at $\delta=2\sqrt{n}$ ?

Question 7.3.

Is there a family of connected regular graphs $G$ with an additive spectral gap slightly less than $2\sqrt{n}$ and with $\gamma(G\pm e)$ not bounded?

Acknowledgments

I am very grateful to Prof. Babai for his guidance and patience, and to Prof. Peter May for organizing the UChicago Math REU.

References

[1] Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak Math. J. (1973), 23(2):298-305. DOI
[2] Noga Alon, Vitali D. Milman. $\lambda_{1}$ , isoperimetric inequalities for graphs, and superconcentrators. J. Combinatorial Theory, Series B (1985), 38:73-88. DOI
[3] Gilbert W. Stewart, Ji-guang Sun. Matrix Perturbation Theory, Academic press, 1990.
[4] Edwin R. van Dam, Willem H. Haemers. Eigenvalues and the Diameter of Graphs. Linear and Multilinear Algebra (1995), 39:33-44. DOI
[5] Andrew Y. Ng, Alice X. Zheng, Michael I. Jordan. Link analysis, eigenvectors and stability. In: 17th Internat. Joint Conf. on A. I. (IJCAI’01), vol. 2, pp. 903-910, Morgan Kaufmann, 2001. Author’s website
[6] Sebastian M. Cioabă, David A. Gregory. Principal eigenvectors of irregular graphs. Electr. J. Linear Algebra (2007), 16:366-379. DOI
[7] Sebastian M. Cioabă, David A. Gregory, Vladimir Nikiforov. Extreme eigenvalues of nonregular graphs. J. Combinatorial Theory, Series B (2007), 97(3):483-486. DOI
[8] Michael Tait, Josh Tobin. Characterizing graphs of maximum principal ratio. Electr. J. Linear Algebra (2018), 34:61-70. DOI

	$\displaystyle\\|\mathbf{p}_{i}-\mathbf{p}_{i-1}\\|$	$\displaystyle=\|M^{-1}(\mathbf{p}_{i-1}e_{21}^{T}\mathbf{p}_{i-1}-\mathbf{p}_{i-2}e_{21}^{T}\mathbf{p}_{i-2})$
		$\displaystyle=\|M^{-1}(\mathbf{p}_{i-1}+\mathbf{p}_{i-2})e_{21}^{T}(\mathbf{p}_{i-1}-\mathbf{p}_{i-2})\|$
		$\displaystyle\leq 2\\|M^{-1}\\|\\|\mathbf{p}_{i-1}\\|\\|\mathbf{p}_{i-1}\\|\cdot\eta\cdot\\|\mathbf{p}_{i-1}-\mathbf{p}_{i-2}\\|$
		$\displaystyle\leq\frac{4\eta^{2}}{\theta^{2}}\\|\mathbf{p}_{i-1}-\mathbf{p}_{i-2}\\|.$

On the principal eigenvector of a graph

Abstract.

1. Introduction

2. General preliminaries

2.1. Graphs

2.2. Matrices, spectra

Definition 2.1.

Definition 2.2.

Fact 2.3.

.

Notation 2.4.

Fact 2.5.

.

2.3. The adjacency operator, principal eigenvector and eigenvalue

Fact 2.6.

Observation 2.7.

.

Corollary 2.8.

.

Corollary 2.9.

Fact 2.10.

Proof.

Fact 2.11.

Fact 2.12.

Fact 2.13.

Proof.

2.4. Spectral gaps

2.5. Rates of growth

2.6. Subgraphs, graph products

Fact 2.14.

Proof.

Notation 2.15.

Notation 2.16.

Notation 2.17.

Observation 2.18.

3. Preliminary results about the principal eigenvector

3.1. Observations and naive bounds on the ratio

Fact 3.1.

Observation 3.2.

Proof.

Corollary 3.3.

.

Corollary 3.4.

Fact 3.5.

Proof.

Fact 3.6.

Proof.

3.2. Chebyshev polynomials and principal eigenvectors

Fact 3.7.

Proof.

Fact 3.8.

Definition 3.9.

Observation 3.10.

Proof.

4. Stability of the ratio: adding or removing edges in bounded distance

Observation 4.1.

Proof.

Observation 4.2.

Proof.

4.1. Adding an edge

Theorem 4.3.

Construction 4.4 (Ringr,d,G2\operatorname{Ring}_{r,d,G_{2}}).

Observation 4.5.

Construction 4.6.

Construction 4.7.

Proposition 4.8.

Proof.

Lemma 4.9.

Proof.

Proof of Theorem 4.3.

4.2. Removing an edge

Theorem 4.10 (Cioabă, Gregory, Nikiforov[7]).

Theorem 4.11.

Lemma 4.12.

Proof.

Proof of Theorem 4.11.

5. Stability of the ratio: multiplicative spectral gap

Definition 5.1.

Theorem 5.2 (N. Alon, V. D. Milman[2]).

Corollary 5.3.

Construction 4.4 ( $\operatorname{Ring}_{r,d,G_{2}}$ ).

6.2.2. Rotating $\mathbf{x}$ to be an eigenvector

6.2.3. Finding small $\mathbf{p}$ when the additive spectral gap is large

6.2.4. Using the bound on $\|\mathbf{p}\|$ to show that $\tilde{\mathbf{x}}$ is the principal eigenvector