# 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.

###### Contents

  1. 1 Introduction
  2. 2 General preliminaries
  3. 3 Preliminary results about the principal eigenvector
  4. 4 Stability of the ratio: adding or removing edges in bounded distance
  5. 5 Stability of the ratio: multiplicative spectral gap
  6. 6 Stability of the ratio: additive spectral gap
  7. 7 Open questions

##  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.

If

(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


different character degrees of irreducible characters in ${\rm
Irr}_{p^{\prime}}(B_{0}(M))$ too. Since every irreducible character in ${\rm
Irr}_{p^{\prime}}(B_{0}(M))$ lies under an irreducible character in ${\rm
Irr}_{p^{\prime}}(B_{0}(G))$ we have that the set of character degrees of
irreducible characters in ${\rm
Irr}_{p^{\prime}}(B_{0}(M))\setminus\\{1_{M}\\}$ is at most $9-k(G/M)$. This,
together with the fact that $3$ does not divide $[G:M]$, forces
$k(G/M)\in\\{1,2,4\\}$.

(2.a.i) If $k(G/M)=1$ then $G=M$, then by Theorem 2.2,
$9=k_{0}(B_{0}(N))=k_{0}(B_{0}(S))^{t}$. Hence either $t=1$ and we are done by
Theorem 3.3 or $t=2$ and $k_{0}(B_{0}(S))=3$. By [NST18, Thm. C], in the
latter case, $|S|_{3}=3$ and then $|P|=9$ as wanted.

(2.a.ii) If $k(G/M)=2$ then $[G:M]=2$, and then
$k_{0}(B_{0}(S))^{t}=k_{0}(B_{0}(N))=k_{0}(B_{0}(M))\leq 1+2\cdot 7=15$. The
above inequalities force $t=2$ and $k_{0}(B_{0}(S))=3$. Then $|P|=9$ by
[NST18, Thm. C].

(2.a.iii) Finally suppose that $k(G/M)=4$. In this case, since there are at
least 5 orbits in ${\rm Irr}(B_{0}(M))\setminus\\{1_{M}\\}$, we have that
every element of ${\rm Irr}_{p^{\prime}}(B_{0}(M))\setminus\\{1_{M}\\}$ has
exactly one element of ${\rm Irr}_{p^{\prime}}(B_{0}(G))$ above it (and there
are exactly 5 orbits in ${\rm Irr}(B_{0}(M))\setminus\\{1_{M}\\}$). Since
${\rm Irr}(B_{0}(G))$ is the unique block covering ${\rm Irr}(B_{0}(M))$ this
means that all the nontrivial elements in ${\rm Irr}_{p^{\prime}}(B_{0}(M))$
are fully ramified in their stabilizers. This means that, if $\varphi\in{\rm
Irr}_{p^{\prime}}(B_{0}(M))$ then $[G_{\varphi}:M]$ is a square. By analyzing
the structure of groups with 4 conjugacy classes we conclude that either
$[G:M]=4$ or $[G:M]=10$ and $G_{\varphi}=M$ for all $\varphi\in{\rm
Irr}_{p^{\prime}}(B_{0}(M))$. If $[G:M]=4$, then
$k_{0}(B_{0}(S))^{t}=k_{0}(B_{0}(N))=k_{0}(B_{0}(M))\leq 1+4\cdot 5=21$ and
then $t=2$ and $k_{0}(B_{0}(S))=3$, as wanted. If $[G:M]=10$, we have that
$k_{0}(B_{0}(S))^{t}=k_{0}(B_{0}(N))=k_{0}(B_{0}(M))=1+10\cdot 5=51$ which
forces $t=1$, contradiction.

(2.b) $k_{0}(B_{0}(G/N))=9$. In this case every height zero character in the
principal block of $G$ contains $N$ in its kernel. But that is absurd. Indeed,
the set ${\rm Irr}_{0}(B_{0}(N))$ has size divisible by $3$. In particular,
also the set of $P$-invariant characters in ${\rm Irr}_{0}(B_{0}(N))$ has size
divisible by 3. Thus, we can choose a $P$-invariant $1_{N}\neq\theta\in{\rm
Irr}_{0}(B_{0}(N))$. By [Isa76, Cor. 8.16], $\theta$ extends to $PN$. By Lemma
2.3, there would be some $\chi\in{\rm Irr}_{0}(B_{0})$ lying over $\theta$, so
not containing $N$ in its kernel.

We have shown that if $N$ is a minimal normal subgroup of $G$ then,
$k_{0}(B_{0}(G/N))\in\\{3,6\\}$.

(2.c) If $k_{0}(B_{0}(G/N))=3$, then $[PN:N]=3$ by [NST18, Thm. C]. We claim
that $N$ is the only minimal normal subgroup of $G$. Once this statement is
proven, we can assume that ${\bf C}_{G}(N)=1$. Suppose tha $M$ is another
minimal normal subgroup of $G$. Since $3$ divides $|M|$ we have that $3$
divides $k_{0}(B_{0}(M))$. Write $K=NM\cong N\times M$. Since $[G:N]_{3}=3$
and $3$ divides $|M|$ we have that $[G:K]$ is not divisible by 3 and
$|M|_{3}=3$. Hence $P\leq K$. Let $L=K{\bf C}_{G}(P)$ which is normal in $G$
by the Frattini argument. By the Alperin-Dade correspondence (Theorem 2.2),
there are the same number of $G$-orbits in ${\rm Irr}_{p^{\prime}}(B_{0}(L))$
as in ${\rm Irr}_{p^{\prime}}(B_{0}(K))={\rm
Irr}_{p^{\prime}}(B_{0}(N))\times{\rm Irr}_{p^{\prime}}(B_{0}(M))$. If $L=G$,
then by Theorem 2.2, we have that
$9=k_{0}(B_{0}(G))=k_{0}(B_{0}(K))=k_{0}(B_{0}(N))k_{0}(B_{0}(M))$, forcing
$k_{0}(B_{0}(N))=k_{0}(B_{0}(M))=3$. Then $|N|_{3}=|M|_{3}=3$ by [NST18, Thm.
C], so $|G|_{3}=9$ as desired. Hence, we may assume that $L<G$.

By Lemma 2.1 we have that $B_{0}(G)$ is the only block covering $B_{0}(L)$.
Notice that by Theorem 3.1, there are at least three characters in both ${\rm
Irr}_{p^{\prime}}(B_{0}(N))$ and ${\rm Irr}_{p^{\prime}}(B_{0}(M))$ with
distinct degrees, namely $\theta_{0}=1_{N}$, $\theta_{1}$ and $\theta_{2}$ for
$N$ and $\varphi_{0}=1_{M}$, $\varphi_{1}$ and $\varphi_{2}$ for $M$. Notice
then that the set

$\Omega=\\{\theta_{i}\times\varphi_{j}\ |\ i,j\in\\{0,1,2\\}\\}\subseteq{\rm
Irr}_{p^{\prime}}(B_{0}(K))$

consists of non-$G$-conjugate characters. In particular, the action of $G$ on
${\rm Irr}_{p^{\prime}}(B_{0}(L))$ defines at least 9 orbits, forcing each
$\chi\in{\rm Irr}_{p^{\prime}}(B_{0})$ to lie above a different $G$-orbit on
$L$. This is absurd as $L<G$ and every character in ${\rm
Irr}(G/L)\subseteq{\rm Irr}_{p^{\prime}}(B_{0})$ lies over $1_{L}$.

Hence the claim is proven and ${\bf C}_{G}(N)=1$. By Theorem 3.3, we may
assume that $t>1$. We claim now that $P$ acts transitively on
$\\{S_{1},\ldots,S_{t}\\}$. Note that $|PN/N|=3$ so each of these $P$-orbits
has length $1$ or $3$.

(2.c.i) Suppose that the action of $P$ on $\\{S_{1},\ldots,S_{t}\\}$ is not
transitive and defines at least one orbit of length $3$. Write $N=R\times T$,
where $R$ is the product of the elements in a $P$-orbit of length 3. Since $P$
acts transitively on the simple factors of $R$, we can argue as in the last
paragraph of the case (2.b) of the proof of Theorem 6.2 to obtain 2 nontrivial
$P$-invariant characters $\theta,\xi\in{\rm Irr}_{p^{\prime}}(B_{0}(R))$ of
different degrees. Now since $|{\rm Irr}_{p^{\prime}}(B_{0}(T))|$ is divisible
by $p$ and $P$ acts on ${\rm Irr}_{p^{\prime}}(B_{0}(T))$, there exists a
nontrivial $P$-invariant $\psi\in{\rm Irr}_{p^{\prime}}(B_{0}(T))$. Notice
that $1_{N}$, $\theta\times 1_{T}$, $\xi\times 1_{T}$,
$\theta\times\psi\in{\rm Irr}_{p^{\prime}}(B_{0}(N))$ are all $P$-invariant
and not $G$-conjugate. By [Isa76, Cor. 8.16], they extend to $PN$. By Theorem
2.7, there are at least $3$ irreducible characters in ${\rm
Irr}_{p^{\prime}}(B_{0}(G))$ above each of them, and no character of $G$ lies
above $2$ of them. This yields $k_{0}(B_{0}(G))>9$, a contradiction.

(2.c.ii) Suppose now that the action of $P$ on $\\{S_{1},\ldots,S_{t}\\}$ is
trivial. Since every $S_{i}$ contains a $P$-invariant irreducible character of
$p^{\prime}$-degree in the principal block, if $t>2$ we can easily construct 3
nontrivial $P$-invariant character in ${\rm Irr}_{p^{\prime}}(B_{0}(N))$ that
are not $G$-conjugate. As in the (2.c.i) case, we get a contradiction using
[Isa76, Cor. 8.16] and Theorem 2.7. We are left with the situation in which
$t=2$ and $P$ normalizes $S_{i}$ for $i\in\\{1,2\\}$. As before, we can derive
a contradiction if we are able to construct $3$ nontrivial $P$-invariant
characters ${\rm Irr}_{p^{\prime}}(B_{0}(N))$ that are not $G$-conjugate. That
is certainly the case if $S$ satisfies the (a1) statement of Theorem 3.1. By
Remark 3.2, we can assume that $S$ satisfies (a2) and that the Sylow
$3$-subgroup of ${\rm Out}(S)$ is cyclic and normal. Notice that ${\rm
Out}(S)$ has only $2$ elements of order $3$. Since $|PN/N|=3$, then it is easy
to show that $G/N$ (that can be identified with a subgroup of ${\rm Out}(S)\wr
C_{2}$ because ${\bf C}_{G}(N)=1$) has only $2$ elements of order $3$.
Henceforth $PN/N\triangleleft G/N$ and $PN\triangleleft G$. At this point, we
can consider $M=PN{\bf C}_{G}(P)$. We have that $M$ is normal in $G$ by the
Frattini argument and $B_{0}$ is the only block covering $B_{0}(M)$ by Lemma
2.1. Also, by Theorem 2.2 we know that $k_{0}(B_{0}(M))=k_{0}(B_{0}(PN))$.
Notice that the set of $P$-invariant characters in ${\rm
Irr}_{p^{\prime}}(B_{0}(S_{i}))$ has size at least $3$ (in our situation it
will be exactly $3$ but it is not really important). Hence the set of
$P$-invariant characters in ${\rm Irr}_{p^{\prime}}(B_{0}(N))$ has size at
least $9$, which translates in $k_{0}(B_{0}(M))=k_{0}(B_{0}(PN))\geq 27$ by
[Nav98, Cor. 9.6]. We then see that $M<G$. As $G/M$ is a group or order
coprime to $3$ and all its characters are contained in $B_{0}(G/N)$ (if they
would lie in a different block of maximal defect of the quotient contained in
$B_{0}(G)$ we would be done just by constructing $2$ nontrivial $P$-invariant
characters in ${\rm Irr}_{p^{\prime}}(B_{0}(N))$ lying in different
$G$-orbits, that we can do), we get that $G/M\cong C_{2}$. Then
$k_{0}(B_{0})\geq 2+26/2\geq 15$, a contradiction.

Therefore we can assume that $P$ acts transitively on the simple direct
factors of $N$ and therefore $t=3$. If $|S|_{3}=3$, then notice that $P$ has a
normal subgroup $Q\cong{C}_{3}\times{C}_{3}\times{C}_{3}$, $|P/Q|=3$ and $P$
acts permuting transitively the ${C}_{3}$-factors of $Q$. In particular,
$[P:P^{\prime}]=9$, as wanted. So we may assume that $9$ divides $|S|$. By
Theorem 3.1(c), notice that $N$ has at least 3 $G$-orbits of $P$-invariant
nontrivial characters (we are reasoning as in the third paragraph of (2.b) in
the proof of Theorem 6.2). Each $G$-orbit has at least 3 characters in the
principal block above by Theorem 2.7, a contradiction.

(2.d) Finally we consider the case where $k_{0}(B_{0}(G/N))=6$. Reasoning as
in case (2.c) we can assume that $P$ acts transitively on the simple direct
factors of $N$. In this case $[PN:P^{\prime}N]=9$ by Theorem 6.2. Suppose that
Theorem 3.1(a1) holds for $S$ and let $\theta_{1},\theta_{2}$ as in Theorem
3.1(a1). Let $\tilde{\theta_{i}}\in{\rm Irr}_{p^{\prime}}(B_{0}(N))$ be the
product of the copies of $\theta_{i}$, so $\tilde{\theta}_{1}$ and
$\tilde{\theta}_{2}$ are $P$-invariant (so they extend to $PN$ by [Isa76, Cor.
8.16]) and not $G$-conjugate. By Lemma 2.3 and Theorem 2.7 each of these
characters have at least 3 irreducible characters in ${\rm
Irr}_{p^{\prime}}(B_{0}(G))$ lying above them, a contradiction. Finally
suppose that Theorem 3.1(a2) holds for $S$ and let $\theta\in{\rm
Irr}_{p^{\prime}}(B_{0}(S))$ be the character given by the statement of
Theorem 3.1(a2). Let $\tilde{\theta}\in{\rm Irr}_{p^{\prime}}(B_{0}(N))$ be
the product of copies of $\theta$, so that $\tilde{\theta}$ is $P$-invariant.
Notice then that $G_{\tilde{\theta}}$ acts transitively on the simple direct
factors of $N$. By Theorem 3.5 we also know that $\tilde{\theta}$ extends to
some $\phi\in{\rm Irr}(B_{0}(G_{\tilde{\theta}}))$. By Lemma 2.8 we have that
$k_{0}(B_{0}(G_{\tilde{\theta}})|\tilde{\theta})\geq
k_{0}(B_{0}(G_{\tilde{\theta}}/N))$. Since $|G_{\tilde{\theta}}:N|_{3}>3$,
then $k_{0}(B_{0}(G/N))>3$ by [NST18, Thm. C], and this gives a contradiction
as $B_{0}$ contains at most 3 characters of degree coprime to $p$ not lying
over $1_{N}$. ∎

### Acknowledgments

The authors are indebted to Miquel Martínez for a careful reading of a
previous version of this preprint and for detecting a missing case in the
proof of Theorem 6.3. We would also like to thank Alex Moretó and Gustavo
Fernández-Alcober for useful discussions on $p$-groups.

## References

  * [Alp76] J. L. Alperin, Isomorphic blocks,  J. Algebra 43 (1976), 694–698.
  * [AE05] J. An, C. Eaton, Modular representation theory of blocks with trivial intersection, Algebr. Represent. Theory 8 (2005), 427–448.
  * [BMM93] M. Broué, G. Malle, and J. Michel, Generic blocks of finite reductive groups, _Astérisque_ 212 (1993), 7–92.
  * [CE04] M. Cabanes and M. Enguehard, _Representation theory of finite reductive groups_ , New Mathematical Monographs 1, Cambridge University Press, Cambridge, 2004.
  * [Car85] R. W. Carter, _Finite groups of Lie type. Conjugacy classes and complex characters_ , John Wiley and Sons, Inc., New York, 1985, 544 pp.
  * [CPW87] G.H. Cliff, W. Plesken and A. Weiss. Order-theoretic properties of the center of a block; in The Arcata Conference on Representations of Finite Groups, Arcata, Calif., 1986, Proc. Sympos. Pure Math. 47 (1987), 413–420.
  * [Dad77] E. C. Dade,  Remarks on isomorphic blocks,  J. Algebra 45 (1977), 254–258.
  * [DZ87] D. I. Deriziotis and G. O. Michler, Character table and blocks of finite simple triality groups ${}^{3}\\!\operatorname{D}_{4}(q)$, _Trans. Amer. Math. Soc. 303_ (1987), 39–70.
  * [DLM97] F. Digne, G. I. Lehrer, and J. Michel, On Gelfand-Graev characters of reductive groups with disconnected centre, _J. Reine Angew. Math. 491_ (1997), 131–147.
  * [FS82] P. Fong and B. Srinivasan,  The blocks of finite general linear and unitary groups,  Invent. Math. 69 (1982), 109–153.
  * [FS89] P. Fong and B. Srinivasan,  The blocks of finite classical groups,  J. reine angew. Math. 396 (1989), 122–191.
  * [GAP] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.11.0, 2020. http://www.gap-system.org
  * [GM20] M. Geck, G. Malle, _The Character Theory of Finite Groups of Lie Type: A Guided Tour_. Cambridge University Press, Cambridge, 2020.
  * [GMS22] E. Giannelli, J. M. Martínez, and A. A. Schaeffer Fry,Character degrees in blocks and defect groups, J. Algebra 594 (2022), 170–193.
  * [GRSS20] E. Giannelli, N. Rizo, B. Sambale, and A. A. Schaeffer Fry, Groups with few $p^{\prime}$-character degrees in the principal block, _Proc. Amer. Math. Soc._ 148 (2020), 4597–4614.
  * [GSV19] E. Giannelli, A. A. Schaeffer Fry, and C. Vallejo, Characters of $\pi^{\prime}$-degree, _Proc. Amer. Math. Soc. 147_, no. 11 (2019), 4697–4712.
  * [GLS98] D. Gorenstein, R. Lyons, and R. Solomon, _The classification of the finite simple groups_ , Number 3, Part I, Chapter A, Almost simple K-groups, Mathematical Surveys and Mono- graphs, 40.3, American Mathematical Society, Providence, RI, 1998.
  * [Hi90] G. Hiss, Regular and semisimple blocks of finite reductive groups, _J. London Math. Soc. (2) 41_ (1990), 63–68.
  * [HiSh90] G. Hiss and J. Shamash, $3$-blocks and $3$-modular characters of $\operatorname{G}_{2}(q)$, _J. Algebra 131_ (1990), 371–387.
  * [HS23] N. N. Hung and A. A. Schaeffer Fry, On Héthelyi-Külshammer’s conjecture for principal blocks, _Algebra Number Theory 17_:6 (2023), 1127–1151.
  * [HSV23] N. N. Hung, A. A. Schaeffer Fry, and C. Vallejo, Height zero characters in principal blocks, _J. Algebra_ , 622 (2023), 197–219.
  * [HSV24] N. N. Hung, A. A. Schaeffer Fry, and C. Vallejo, The principal blocks with 6 irreducible characters. To appear in J. Algebra, special issue dedicated to Georgia Benkart.
  * [Isa76] I. M. Isaacs, Character theory of finite groups, AMS Chelsea Publishing, Providence, RI, 2006.
  * [Isa08] I. M. Isaacs, Finite group theory, volume 92 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2008.
  * [J78] G. James, _The representation theory of the symmetric groups_ ,  Lecture Notes in Mathematics, vol. 682, Springer, Berlin, 1978.
  * [JK81] G. James and A. Kerber, _The representation theory of the symmetric group_ ,  Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley Publishing Co., Reading, Mass., 1981.
  * [Lan81] P. Landrock, On the number of irreducible characters in a $2$-block, _J. Algebra_ 68 (1981), 426–442.
  * [Lar23] A. Laradji, On height zero characters of $p$-solvable groups, Osaka J. Math. 60 (2023), 753–759.
  * [Lub] F. Lübeck, Character Degrees and their Multiplicities for some Groups of Lie Type of Rank $<9$, https://www.math.rwth-aachen.de/~Frank.Luebeck/chev/DegMult/index.html
  * [Mal90] G. Malle, Die unipotenten Charaktere von ${}^{2}\\!\operatorname{F}_{4}(q^{2})$, _Comm. Algebra 18_ (1990), 2361–2381.
  * [Mal91] G. Malle, The maximal subgroups of ${}^{2}\\!\operatorname{F}_{4}(q^{2})$, _J. Algebra 139_ (1991), 52–69.
  * [Mal07] G. Malle, Height $0$ characters of finite groups of Lie type, _Represent. Theory_ 11 (2007), 192–220.
  * [Mal08] G. Malle, Extensions of unipotent characters and the inductive McKay condition, _J. Algebra_ 320 (2008), 2963–2980.
  * [Mal20] G. Malle, On the number of characters in blocks of quasi-simple groups, _Algebr Represent Theor 23_ (2020), 513–539.
  * [MT11] G. Malle and D. Testerman, _Linear Algebraic Groups and Finite Groups of Lie Type_. Cambridge Studies in Advanced Mathematics, 133, Cambridge University Press, Cambridge, 2011.
  * [MO83] G. O. Michler and J. B. Olsson, Character correspondences in finite general linear, unitary and symmetric groups, _Math. Z._ 184, 203–233.
  * [Mur94] M. Murai, Block induction, normal subgroups and characters of height zero, Osaka J. Math. 31 (1994), 9–25.
  * [Nav98] G. Navarro,  Characters and blocks of finite groups, London Mathematical Society Lecture Note Series 50,  Cambridge University Press, Cambridge, 1998.
  * [Nav18] G. Navarro, _Character theory and the McKay conjecture_ , Cambridge Studies in Advanced Mathematics 175, Cambridge University Press, Cambridge, 2018\.
  * [NRSV21] G. Navarro, N. Rizo, A. a. Schaeffer Fry, C. Vallejo, characters and generation of Sylow 2-subgroups, Rep. Theory AMS 25 (2021), 142–165.
  * [NS23] G. Navarro, B. Sambale, Characters, commutators and centers of Sylow subgroups, Rep. Theory AMS 27 (2023), 717–733.
  * [NST18] G. Navarro, B. Sambale, P. H. Tiep, Characters and Sylow 2-subgroups of maximal class revisited, _J. Pure Appl. Algebra_ 222 (2018), 3721–3732.
  * [NT13] G. Navarro and P. H. Tiep, Characters of relative $p^{\prime}$-degree over normal subgroups, _Ann. Math._ 178:3 (2013) 1135–1171.
  * [NV17] G. Navarro, C. Vallejo, 2-Brauer correspondent blocks with one simple module, _J. Algebra_ 488 (2017), 230–243.
  * [Ols76] J. B. Olsson, McKay numbers and heights of characters, _Math. Scand. 38_ (1976), 25–42.
  * [Ols93] J. B. Olsson, _Combinatorics and representations of finite groups_ , Universität Essen, Fachbereich Mathematik, Essen, 1993.
  * [Ols90] J. B. Olsson, On the $p$-blocks of Symmetric and Alternating groups and their covering groups, _J. Algebra_ 128 (1990), 188–213.
  * [Riz19] N. Rizo, p-Blocks relative to a character of a normal subgroup, _J. Algebra_ 514 (2018), 254–272.
  * [RSV20] N. Rizo, A. A. Schaeffer Fry, and C. Vallejo, Galois action on the principal block and cyclic Sylow subgroups, _Algebra Number Theory 14_:7 (2020), 1953–1979.
  * [RSV21] N. Rizo, A. A. Schaeffer Fry, and C. Vallejo, Principal blocks with 5 irreducible characters, _J. Algebra_ 585 (2021), 316–337.
  * [Ro96] D.J.S. Robinson, _A Course in the Gheory of Groups_ , Graduate Texts in Mathematics Vol. 80, Springer, 1996.
  * [Sam14] B. Sambale, _Blocks of finite groups and their invariants_ , Lecture Notes in Mathematics 2127, Springer, Cham, 2014.
  * [Spa12] B. Spaeth, Inductive McKay condition in defining characteristic, _Bull. Lond. Math. Soc. 44_ (3) (2012), 426–438.
  * [Sri68] B. Srinivasan, The characters of the finite symplectic group ${\mathrm{Sp}}(4,q)$, _Trans. Amer. Math. Soc. 131_ no. 2 (1968), 488–525.
  * [Tau37] O. Taussky, A remark on the class field towers, J. London Math. Soc. 1 (1937), 82–85.
  * [Tay18] J. Taylor, Action of automorphisms on irreducible characters of symplectic groups, _J. Algebra 505_ (2018), 211–246.
  * [Wa66] H. N. Ward, On Ree’s series of simple groups, _Trans. Amer. Math. Soc. 121(1)_ (1966), 62–89.
  * [We55] A. J. Weir, Sylow $p$-subgroups of the classical groups over finite fields with characteristic prime to $p$, _Proc. Amer. Math. Soc. 6_, No. 4 (1955), 529–533.


# Deployment of UAVs for Optimal Multihop Ad-hoc Networks Using Particle Swarm
Optimization and Behavior-based Control

Ngan Duong Thi Thuy, Duy Nam Bui, Manh Duong Phung and Hung Pham Duy Ngan
Duong Thi Thuy, Duy Nam Bui and Hung Pham Duy are with the VNU University of
Engineering and Technology, Hanoi, Vietnam<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Duong Phung is with the
Fulbright University Vietnam, Ho Chi Minh City, Vietnam.
<EMAIL_ADDRESS>research has been done under the research
project QG.21.26 “Resilience for Preserving Multi-Robot Network in Dynamic
Environment” of Vietnam National University, Hanoi.

###### Abstract

This study proposes an approach for establishing an optimal multihop ad-hoc
network using multiple unmanned aerial vehicles (UAVs) to provide emergency
communication in disaster areas. The approach includes two stages, one uses
particle swarm optimization (PSO) to find optimal positions to deploy UAVs,
and the other uses a behavior-based controller to navigate the UAVs to their
assigned positions without colliding with obstacles in an unknown environment.
Several constraints related to the UAVs’ sensing and communication ranges have
been imposed to ensure the applicability of the proposed approach in real-
world scenarios. A number of simulation experiments with data loaded from real
environments have been conducted. The results show that our proposed approach
is not only successful in establishing multihop ad-hoc routes but also meets
the requirements for real-time deployment of UAVs.

###### Index Terms:

Unmanned aerial vehicles (UAVs), ad-hoc network, search and rescue, particle
swarm optimization, behavior control

##  I Introduction

When natural disasters happen, it is critical to maintain communication
channels between the affected areas and rescue coordination centers to
effectively coordinate search and rescue operations. An emergency wireless
network is typically needed as existing communication infrastructure is either
damaged or destroyed during the disaster. Ad-hoc networks provide a relevant
solution in this scenario since they are reliable in harsh conditions and can
be deployed quickly without requiring existing communication infrastructure
[1, 2]. The use of these networks has been discussed in [3, 4, 5] where
satellites, mobile devices, and remaining active base stations are utilized to
form the networks. However, the flexibility and scalability of these networks
are still limited due to their dependence on remaining active devices, which
are hard to manage during a disaster.

Recently, unmanned aerial vehicles (UAVs) have shown their potential to search
and rescue applications thanks to their mobility in working environments and
capability of carrying different types of sensors [6, 7, 8]. Several works
have been conducted to address issues related to UAV-based network
communication such as routing protocols [9], data authentication schemes [10],
topology control [11], and medium access control [12]. However, the location
allocation and routing problems for UAVs in unknown environments are hardly
addressed. When establishing a multihop ad-hoc route, it is necessary to
optimize the position of UAV nodes for efficient signal transmission. The
route to navigate each UAV to its goal position should also be determined to
ensure safe operation of the UAV.

In this work, we propose a new approach to deploying multiple UAVs to
establish an ad-hoc network in unknown environments. First, we search for the
optimal position of each UAV by formulating it as an optimization problem and
then use particle swarm optimization (PSO) to solve it. A behavior-based
target tracking control is then proposed to navigate the UAVs to their optimal
positions while avoiding obstacles. Simulation results show that the proposed
approach can establish a communication channel between the base station and
the disaster area in complex environments. The computed positions and routes
are also safe and efficient for UAV operation.

##  II Problem formulation

(a) Creation of a multihop ad-hoc route

(b) The UAV model with its sensing and communication ranges

Figure 1: The multihop ad-hoc network and UAV model. Figure 2: Deployment
approach diagram

This work focuses on establishing an optimal multihop ad-hoc route that
connects a base station to a disaster area via a sequence of UAV nodes, as
illustrated in Fig. 1(a). The UAVs act as intermediate routers to relay
messages. Each UAV is equipped with a GPS module and an inertial measurement
unit (IMU) to determine its position and orientation with respect to a global
coordinate system. We assume that the UAV has a sensory system that can detect
obstacles and a network module that is capable of carrying out peer-to-peer
communication with other UAVs within its range. We also assume that the number
of UAVs is sufficient and the disaster area’s location is known.

###  II-A UAV model and constraints

The UAV is modelled as a particle with position $P=\left[x,y,z\right]^{T}$ and
heading angle $\psi$, as illustrated in Fig. 1(b). The safe zone of the UAV is
represented as the area surrounded by a circle with a radius of $S$. The
communication and sensing ranges are represented by circles with the radii of
$R_{C}$ and $R_{S}$, respectively. Noting that the sensing range is typically
much small than the communication. Let $V=\left[v_{x},v_{y},v_{z}\right]^{T}$
be the UAV’s velocity. The position and orientation of the UAV after each time
step $T$ are updated as follows:

$\displaystyle P\left(t+T\right)$
$\displaystyle=P\left(t\right)+V\left(t\right)T$ (1)
$\displaystyle\psi\left(t+T\right)$
$\displaystyle=\text{atan2}\left(v_{y},v_{x}\right)$

To form an ad-hoc network, the following constraints must be satisfied:

  1. (i)

Each UAV stays within the communication range of its adjacent UAVs.

  2. (ii)

Each UAV maintains a safe distance from obstacles and a suitable altitude
above the ground during its operation.

###  II-B Deployment approach

In this work, our approach to deploying UAVs is illustrated in Fig. 2. UAVs
are being deployed sequentially in which each UAV concurrently searches for
the next optimal position within its sensing range until reaching the
communication boundary. The found position closest to the communication
boundary is then chosen as the final position for that UAV. After that, the
next UAV will be dispatched to first go to the last found optimal position and
then carry out the search process to find its optimal location. The process is
repeated until the target is reached. We use PSO to search for optimal
positions and a behavior-based controller to navigate the UAVs to those
positions.

##  III PSO-based optimal position identification

This section describes our approach to find optimal positions for UAVs to
establish a multihop ad-hoc communication route from the base station to the
disaster area.

###  III-A Fitness function definition

The search process is formulated as an optimization problem that recursively
looks for the optimal intermediate point $P_{inew}$ within the UAV’s sensing
range $R_{S}$ until reaching its communication limit $R_{C}$. The search for
$P_{inew}$ is carried out by fulfilling the following criteria: 1) minimizing
the angle between the UAV and the target, 2) maintaining the UAV’s location
within the proximity of its neighbors’ communication range, 3) avoiding
obstacles. Hence, the fitness function is designed in the form:

$F=\sum_{k=1}^{4}b_{k}F_{k}$ (2)

where $b_{k}$ is the weight coefficient and $F_{k}$ is the cost associated to
search criterion $k$. In this work, we define $F_{1}$ for obstacle avoidance,
$F_{2}$ for target angle minimization and $F_{3}$ and $F_{4}$ for optimizing
the sensing and communication links.

####  III-A1 Avoiding obstacles

Assume that the UAV has a size of $D$. At height $z$, an obstacle can be
represented by a circle with center $C_{k}$ and radius $R_{k}$. To avoid
obstacles, the UAV needs to maintain a safe distance $S$ to the obstacles’
boundary as illustrated in Fig. 3. Let $P_{i}$ be the location of UAV $i$ and
$d_{k}$ be the distance between $P_{i}$ and $C_{k}$. The objective function
for obstacle avoidance is defined as follows:

$F_{1}=\left\\{\begin{array}[]{cc}0&\text{if }d_{k}>R_{k}+D+S\\\
R_{k}+D+S-d_{k}&\text{if }R_{k}+D<d_{k}\leq R_{k}+D+S\\\ \infty&\text{if
}d_{k}\leq R_{k}+D\end{array}\right.$ (3)

####  III-A2 Minimizing the target angle

Assume the disaster area is known and its center $E$ is the target location
for UAVs’ deployment. The target angle $\alpha_{i}$ is then defined as the
angle between the vector $\overrightarrow{P_{i}P_{inew}}$ from the current
position $P_{i}$ to the next search position $P_{inew}$ and the vector
$\overrightarrow{P_{i}E}$ towards the target as illustrated in Fig. 4. The
next position to deploy the UAV is expected to have the smallest target angle,
i.e., closest to the line of sight (LOS) between the base station and the
target. Thus, the objective function to minimize the target angle is defined
as follows:

$F_{2}=\alpha_{i}=\text{atan2}\left({\left\|\overrightarrow{P_{i}P_{inew}}\times\overrightarrow{P_{i}E}\right\|,\overrightarrow{P_{i}P_{inew}}\cdot\overrightarrow{P_{i}E}}\right)$
(4)

where operators ‘$\times$’ and ‘$\cdot$’ are the cross and dot products,
respectively.

####  III-A3 Optimizing communication links

During the deployment process, the communication link between two adjacent
UAVs needs to be optimized to ensure communication quality and minimize the
number of UAVs used. For that, the location of the next UAV must be within the
communication range of its adjacent ones.

Let $P_{i}$, $P_{inew}$, and $P_{i-1}$ be respectively the positions of the
current UAV, the optimal point, and the previous adjacent node. Denote $c_{i}$
and $r_{i}$ as the distances between $P_{i-1}$ and $P_{i}$, and $P_{i}$ and
$P_{inew}$, respectively. The objective functions to optimize those distances
are defined as follows:

$F_{3}=\left\\{\begin{array}[]{cc}\left|R_{S}-r_{i}\right|&\text{if }r_{i}\leq
R_{S}\\\ \infty&\text{otherwise}\end{array}\right.$ (5)
$F_{4}=\left\\{\begin{array}[]{cc}\left|R_{C}-c_{i}\right|&\text{if }c_{i}\leq
R_{C}\\\ \infty&\text{otherwise}\end{array}\right.$ (6)

###  III-B Optimal location identification using PSO

The PSO algorithm is used to minimize $F$ to find the best positions for UAVs
due to its fast convergence and robustness in solving complex optimization
problems [13, 14]. It works based on swarm intelligence in which a set of
particles is first initiated with random positions. Their positions are then
adjusted based on two learning parameters, $gbest$, the best position of the
swarm, and $pbest_{i}$, the best position of particle $i$. Let $v_{i}(t)$ be
the velocity of particle $i$ at time $t$. Its position $x_{i}(t)$ is then
updated according to the following equations:

$\displaystyle v_{i}(t+1)$
$\displaystyle=\text{$\omega$}v_{i}(t)+c_{1}r_{1}(pbest_{i}(t)-x_{i}(t))$ (7)
$\displaystyle+c_{2}r_{2}(gbest(t)-x_{i}(t))$ $\displaystyle x_{i}(t+1)$
$\displaystyle=x_{i}(t)+v_{i}(t+1)$

where $\omega$ is the inertia coefficient; $c_{1}$, $c_{2}$ are respectively
the individual and global acceleration coefficients; and $r_{1}$, $r_{2}$ are
two random values in the range of $(0,1)$.

Result: Optimal position

1 Initialize: PSO population, $gbest$, and $IterMax$

2 Observe obstacles in environment

3 for  _$k\leftarrow 1$ to $IterMax$_ do

4 for  _Particle $i$ in PSO Population_ do

5 Calculate cost value $F$ of Particle $i$ by Eq. (2)

6 Evaluate and Update $pbest_{i}$

7 Evaluate and Update $gbest$

8 Update velocities $v_{i}$ and positions $x_{i}$ by Eq. (7)

9

10

Algorithm 1 PSO-based optimal location identification

The implementation of PSO to find UAVs’ optimal position is described in
Algorithm 1. Initially, a set of particles is generated with random positions,
each represents a possible position of the UAV. Obstacles in the searching
area are also identified by the UAV’s sensor. The searching process then
starts in which each particle $i$ calculates its fitness value using Eq. (2).
The best cost values of particle $i$, $pbest_{i}$, and of the swarm, $gbest$,
are then updated. Finally, the velocity $v_{i}$ and position $x_{i}$ of
particle $i$ are updated by Eq. (7). The process is repeated until the maximum
number of iterations is reached. The position associated with the final
$gbest$ value is chosen as the optimal position for the UAV.

Figure 3: Obstacle avoidance illustration Figure 4: Illustration of the target
angle $\alpha$

##  IV Behavior-based Target Tracking

(a) Move to the target

(b) Avoid obstacles

(c) Avoid other UAVs

Figure 5: Sub-behaviors of UAVs

After finding the optimal position $P_{i}$ for UAV $i$, the deployment of the
UAV continues by first navigating it to $P_{i}$ and then repeating the search
process to find the optimal position $P_{i+1}$. To navigate the UAV to
$P_{i}$, we design a behavior-based target tracking controller that combines
several sub-behavior of the form:

$V=f_{m2g}V_{m2g}+f_{ath}V_{ath}+f_{adr}V_{adr},$ (8)

where $V_{m2g}$, $V_{ath}$, $V_{adr}$ are respectively the sub-behaviors for
moving to the target, avoiding obstacles, and avoiding other UAVs, and
$f_{m2g}$, $f_{ath}$, $f_{adr}$ are control parameters. The definition of sub-
behavior is described as follows.

###  IV-A Move-to-target behavior

The aim of the move-to-target behavior is to drive the UAV toward its target
position as illustrated in Fig. 5(a). Denote the target position as
$P_{d}=\left[x_{d},y_{d},z_{d}\right]^{T}$. The move-to-target behavior is
defined as:

$V_{m2g}=\dfrac{1}{d_{m2g}}\left[\begin{array}[]{c}x_{d}-x\\\ y_{d}-y\\\
z_{d}-z\end{array}\right]$ (9)

where $d_{m2g}$ is the distance from the UAV to its target $P_{d}$. The
control parameter for this behavior is defined as follows:

$f_{m2g}\left(d_{m2g}\right)=\left\\{\begin{array}[]{cc}a_{m2g}&\text{if
}d_{m2g}\geq b_{m2g}\\\ a_{m2g}\dfrac{d_{m2g}}{b_{m2g}}&\text{if
}d_{m2g}<b_{m2g}\end{array}\right.$ (10)

where $a_{m2g}$ and $b_{m2g}$ are pre-defined constants.

###  IV-B Obstacle avoidance behavior

When an obstacle is detected, the UAV activates its avoidance behavior. With
this behavior, the direction of the UAV’s movement is changed by $90$ degrees
relative to the direction towards the obstacle and the rotation angle $\gamma$
is changed depending on the direction of the target as illustrated in Fig.
5(b). Assume that at height $z$, the obstacle is modeled as a circle with
center $\left(x_{th},y_{th}\right)$ and radius $r_{th}$. The obstacle
avoidance behavior is then expressed as:

$V_{ath}=\dfrac{1}{d_{ath}}\text{Rot}_{z}\left(-\dfrac{\pi}{2}\text{sgn}\left(\rho\right)\right)\left[\begin{array}[]{c}x_{th}-x\\\
y_{th}-y\\\ z\end{array}\right]$ (11)

where $d_{ath}$ is the distance from the UAV to the obstacle, Rotz represents
the rotation about the $z$-axis, and sgn(.) denotes the sign function. The
rotation angle $\gamma$ is determined as follows:

$\rho=\sin\gamma=\dfrac{x_{th}-x}{d_{ath}}\sin\psi-\dfrac{y_{th}-y}{d_{ath}}\cos\psi$
(12)

The control parameter for the obstacle avoidance behavior is given as follows:

$f_{ath}\left(d_{ath}\right)=\left\\{\begin{array}[]{cc}0&\text{if
}d_{ath}\geq b_{ath}\\\
a_{ath}\left(1-\dfrac{d_{ath}}{b_{ath}}\right)&\text{if
}d_{ath}<b_{ath}\end{array}\right.$ (13)

where $a_{ath}$ and $b_{ath}$ are the adjustable parameters.

###  IV-C Avoiding collision with other UAVs

The behavior to avoid collision with other UAVs is activated when one UAV is
too close to another. As illustrated in Fig. 5(c), the avoidance is carried
out based on control vector $V_{adr}$ that drives the UAV to move away from
the other. Let $d_{adr}$ be the distance between two UAVs, and
$P_{dr}=\left[x_{dr},y_{dr},z_{dr}\right]^{T}$ be the position of the UAV to
be avoided. The collision avoidance behavior is formulated as follows:

$V_{adr}=\dfrac{1}{d_{adr}}\left[\begin{array}[]{c}x_{dr}-x\\\ y_{dr}-y\\\
z_{dr}-z\end{array}\right]$ (14)

The control parameter of this behavior is given as:

$f_{adr}\left(d_{adr}\right)=\left\\{\begin{array}[]{cc}0&\text{if
}d_{adr}\geq b_{adr}\\\
a_{adr}\left(1-\dfrac{d_{adr}}{b_{adr}}\right)&\text{if
}d_{adr}<b_{adr}\end{array}\right.$ (15)

where $a_{adr}$ and $b_{adr}$ are pre-defined constants.

##  V Multihop Ad-hoc Route Deployment

1switch  _state_ do

2 case  _Unassigned_ do

3 Be in idle

4 if  _be its turn and get target_ then

5 state $\leftarrow$ Assigned

6

7

8

9 case  _Assigned_ do

10 Get $current\\_node$, $target\\_node$

11 if  _( $current\\_node$ != $target\\_node$)_ then

12 Move to $current\\_node$ by Behavior-based controller

13 $current\\_node$ = $next\\_node$

14 else

15 state $\leftarrow$ Explore

16

17 case  _Explore_ do

18

19 if  _Not existing Target_ then

20 Target searching using PSO (Algorithm 1)

21 if  _Reach limited range or destination_ then

22 state $\leftarrow$ Occupied

23

24 else

25 Move to $target$ by Behavior-based controller

26 if  _Reach target_ then

27 Hover

28

29

30

31 case  _Occupied_ do

32 if  _Reach destination_ then

33 Multihop ad-hoc route is done

34 else

35 Broadcast current location until assigned

36

37

38

Algorithm 2 Multihop Ad-hoc Communication Route Deployment Strategy

In this section, we present the strategy to deploy UAVs to form a multihop ad-
hoc communication network from the base station to the disaster area using the
PSO and behavior-based controller111Source code of the strategy can be found
at https://github.com/duynamrcv/uav_multihop_adhoc. As shown in Algorithm 2,
the strategy uses four states named unassigned, assigned, explore, and
occupied as in [15] to deploy each UAV as follows.

“Unassigned” (lines 2-7): the UAV is idle at the base station and waits to be
deployed. If it receives the position and in-turn messages from the current
deploying UAV, it changes its state to “Assigned”.

“Assigned” (lines 8-17): the UAV is assigned a target which is the optimal
position found by the last UAV. It then flies to the target using the
behavior-based controller. During the flight, the UAV needs to go through the
established nodes. When reaching the target, its state is changed to
“Explore”.

“Explore” (lines 18-31): the UAV explores the next optimal intermediate
position within its sensing range using the PSO algorithm. It then repeats the
exploration process until reaching its communication range. The last optimal
intermediate position is set as the final position of the UAV. The UAV hovers
at that position and changes its state to “Occupied”.

“Occupied” (lines 32-38): the UAV is hovering at its optimal position. If that
position is not the destination, the UAV will broadcast its position to the
unassigned UAVs until a UAV is dispatched. Otherwise, the establishment of the
multihop ad-hoc route is completed.

TABLE I: Results of the UAV deployment compared to the ideal reference Scen. | UAV | Ideal position | Actual position | Target Angle (rad) | Time consuming (s) |  Link length (m) |  Temporary goal number
---|---|---|---|---|---|---|---
Ideal | Actual | Searching | Deployment
1 | 1 | $\left[405.92,318.04,323.47\right]^{T}$ | $\left[430.38,280.78,328.26\right]^{T}$ | 0.8140 | 0.6653 | 12.05 | 21.05 | 293.06 | 7
2 | $\left[611.85,536.07,330.98\right]^{T}$ | $\left[669.47,452.65,367.33\right]^{T}$ | 0.6233 | 15.21 | 46.19 | 297.04 | 9
3 | $\left[817.77,754.11,338.49\right]^{T}$ | $\left[818.47,706.88,351.12\right]^{T}$ | 1.0407 | 11.76 | 60.45 | 295.12 | 7
4 | $\left[880,820,340.70\right]^{T}$ | $\left[878.70,817.88,344.90\right]^{T}$ | 1.0737 | 5.47 | 69.76 | 126.44 | 4
2 | 1 | $\left[387.38,334.23,332.65\right]^{T}$ | $\left[357.74,349.55,328.01\right]^{T}$ | 0.8961 | 1.0071 | 13.17 | 20.91 | 295.44 | 7
2 | $\left[574.77,568.46,329.35\right]^{T}$ | $\left[584.39,539.50,322.09\right]^{T}$ | 0.6975 | 15.41 | 42.94 | 295.78 | 8
3 | $\left[762.15,802.69,336.04\right]^{T}$ | $\left[798.24,741.52,350.71\right]^{T}$ | 0.7570 | 14.89 | 63.21 | 295.57 | 8
4 | $\left[800,850,337.39\right]^{T}$ | $\left[799.29,845.82,339.34\right]^{T}$ | 1.5607 | 4.031 | 68.00 | 104.92 | 3

##  VI Results

To evaluate the performance of the proposed approach, we have carried out a
number of simulation experiments. Two scenarios are generated by using the
digital elevation model (DEM) map [16] augmented with additional obstacles as
shown in Fig. 6. The distance between the base station and the destination is
chosen as 1000 m in both scenarios. The UAV has $D=1$ m, $S=10D$, $R_{C}=300$
m, and $R_{S}=50$ m. The PSO is set with the population size of 100, $w=1$
with a damping ratio of $0.98$, $c_{1}=c_{2}=1.5$, and $IterMax=100$. The
behavior-based target tracking control is set with $a_{m2g}=30.0$,
$b_{m2g}=20.0$, $a_{ath}=30.0$, $b_{ath}=15.0$, $a_{adr}=30.0$ and
$b_{adr}=20.0$. With this setup, the system requires 4 UAVs to form a multihop
ad-hoc route.

Figure 6 shows the deployment results222Video showing the proposed strategy
deployment process: https://youtu.be/5w8bz2UjB94. In both scenarios, $4$ UAVs
have been successfully deployed as ad-hoc nodes (blue circles) located evenly
along the route with an average link length of 295 m (excluding the link to
the destination), which is close to the communication range of 300 m. The
trajectory of each UAV consists of two segments corresponding to its operation
in the “Assigned” and “Explore” states. Both segments have safe distances from
obstacles. The first segment is the result of the behavior-based controller
when the UAV flies along the route to reach the last node. The second segment
is obtained by the PSO when it guides the UAV through intermediate points,
marked by black dots, until reaching the communication boundary. The number of
intermediate points depend on the ratio between the sensing and the
communication ranges. Noting that the paths generated by the behavior-based
controller need to go through the nodes occupied by the UAVs (blue circles),
but not the intermediate points (black dots) since those points are found
during the exploration process and maybe not globally optimal.

Fig. 7 shows the fitness values over iterations when the PSO looks for optimal
positions. It can be seen that the algorithm quickly converges after 30 to 50
iterations. In addition, the fitness values decrease when the UAV approaches
its final optimal position. Table I shows the data obtained from two
simulation experiments in which the ideal position and target angle are
determined along the line of sight between the base station and destination.
The data shows that the actual positions are close to their ideal references
with an average deviation of 70 m. The actual target angles are also close to
their ideal values with an average deviation of 0.2 rad. The deviations are
mainly caused by obstacles appeared in the environment.

(a) Scenario 1

(b) Scenario 2

Figure 6: Results of the UAV deployment for multihop ad-hoc communication
routes

(a) Scenario 1

(b) Scenario 2

Figure 7: Convergence rate of the PSO-based optimal position searching
algorithm

In terms of time, the system requires an average time of 5 minutes to complete
the deployment at the UAV’s velocity of 15 m/s. The searching for an optimal
point using PSO takes about 1 s, which is sufficient since the UAV will take
at least 3.3 s to fly from one point to another due to its 50 m sensing range.
The behavior-based controller only requires milliseconds to compute the
control command due to its simplicity in computation. The proposed algorithms
therefore can be used for real-time deployment of UAVs. They are also scalable
for larger distances since the computation does not depend on the sensing or
communication range.

##  VII Conclusion

In this work, we have presented a new approach to form a multihop ad-hoc route
to provide communication for disaster response scenarios using a distributed
UAV system. The proposed approach is a combination of a searching method based
on the PSO algorithm to find optimal positions to place network nodes and a
distributed behavior-based controller to coordinate the UAVs to move along the
established route to reach their desired position while avoiding collisions
with obstacles and other UAVs. The evaluation results show that the proposed
approach can establish ad-hoc networks in complex environments with many
obstacles. The deployed positions of the UAVs and the flight paths are close
to their ideal values. The computation time is also sufficient for real-time
operation. Those results confirm the efficiency and applicability of our
method for real-world scenarios.

## References

  * [1] D. G. Reina, M. Askalani, S. L. Toral, F. Barrero, E. Asimakopoulou, and N. Bessis, “A survey on multihop ad hoc networks for disaster response scenarios,” _International Journal of Distributed Sensor Networks_ , vol. 11, no. 10, p. 647037, 2015.
  * [2] M. Conti and S. Giordano, “Mobile ad hoc networking: milestones, challenges, and new research directions,” _IEEE Communications Magazine_ , vol. 52, no. 1, pp. 85–96, 2014.
  * [3] S. S. Anjum, R. M. Noor, and M. H. Anisi, “Review on manet based communication for search and rescue operations,” _Wireless personal communications_ , vol. 94, no. 1, pp. 31–52, 2017.
  * [4] T. D. Ta, T. D. Tran, D. D. Do, H. V. Nguyen, Y. V. Vu, and N. X. Tran, “Gps-based wireless ad hoc network for marine monitoring, search and rescue (msnr),” in _2011 Second International Conference on Intelligent Systems, Modelling and Simulation_ , 2011, pp. 350–354.
  * [5] V. Tundjungsari and A. Sabiq, “Android-based application using mobile adhoc network for search and rescue operation during disaster,” in _2017 International Conference on Electrical Engineering and Computer Science (ICECOS)_ , 2017, pp. 16–21.
  * [6] V. T. Hoang, M. D. Phung, T. H. Dinh, and Q. P. Ha, “System architecture for real-time surface inspection using multiple UAVs,” _IEEE Systems Journal_ , vol. 14, no. 2, pp. 2925–2936, 2020.
  * [7] Y. Zhou, B. Rao, and W. Wang, “Uav swarm intelligence: Recent advances and future trends,” _IEEE Access_ , vol. 8, 2020.
  * [8] M. D. Phung and Q. P. Ha, “Motion-encoded particle swarm optimization for moving target search using UAVs,” _Applied Soft Computing_ , vol. 97, p. 106705, 2020.
  * [9] J.-A. Maxa, M. S. B. Mahmoud, and N. Larrieu, “Secure routing protocol design for uav ad hoc networks,” in _2015 IEEE/AIAA 34th Digital Avionics Systems Conference (DASC)_. IEEE, 2015, pp. 4A5–1.
  * [10] J. Sun, W. Wang, L. Kou, Y. Lin, L. Zhang, Q. Da, and L. Chen, “A data authentication scheme for uav ad hoc network communication,” _The Journal of Supercomputing_ , vol. 76, no. 6, pp. 4041–4056, 2020.
  * [11] Z. Zhao and T. Braun, “Topology control and mobility strategy for uav ad-hoc networks: A survey,” in _Joint ERCIM eMobility and MobiSense workshop_. Citeseer, 2012, pp. 27–32.
  * [12] M. Y.-K. Chua, F. R. Yu, J. Li, Y. Zhou, and L. Lamont, “Medium access control for unmanned aerial vehicle (uav) ad-hoc networks with full-duplex radios and multipacket reception capability,” _IEEE Transactions on Vehicular Technology_ , vol. 62, no. 1, pp. 390–394, 2012.
  * [13] R. Poli, J. Kennedy, and T. Blackwell, “Particle swarm optimization,” _Swarm intelligence_ , vol. 1, no. 1, pp. 33–57, 2007.
  * [14] M. D. Phung and Q. P. Ha, “Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization,” _Applied Soft Computing_ , vol. 107, p. 107376, 2021.
  * [15] P. D. Hung, T. Q. Vinh, and T. D. Ngo, “Distributed coverage control for networked multi-robot systems in any environments,” in _2016 IEEE International Conference on Advanced Intelligent Mechatronics (AIM)_ , 2016, pp. 1067–1072.
  * [16] Geoscience Australia, “Digital elevation model (dem) of australia derived from lidar 5 metre grid,” 2015.