%submitted to E-JC 3/17 \documentclass[12pt]{article} \usepackage{e-jc} \usepackage{tikz} \usepackage{mathtools} \usepackage{amssymb} \usepackage{bbm} \usepackage{amsthm} \usepackage{subcaption} \usepackage{epstopdf} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\vol}{{\rm vol}} \newcommand{\ignore}[1]{} \renewcommand{\today}{} \begin{document} \title{\bf The Spectral Gap of Graphs\\ Arising From Substring Reversals} \author{Fan Chung \qquad Josh Tobin\\ \small Department of Mathematics\\[-0.8ex] \small University of California, San Diego\\[-0.8ex] \small \tt \{fan,rjtobin\}@ucsd.edu } \date{\dateline{June 27, 2017}{XX}\\ \small Mathematics Subject Classifications: 05C50} \maketitle \begin{abstract} The substring reversal graph $R_n$ is the graph whose vertices are the permutations $S_n$, and where two permutations are adjacent if one is obtained from a substring reversal of the other. We determine the spectral gap of $R_n$, and show that its spectrum contains many integer values. Further we consider a a family of graphs that generalize the prefix reversal (or pancake flipping) graph, and show that every graph in this family has adjacency spectral gap equal to one. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% SECTION ONE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} Consider a permutation $\tau$ in the symmetric group $S_n$, which we will write in word notation $(\tau_1, \tau_2, \cdots, \tau_n)$, where we denote $\tau(i) = \tau_i$. A \textit{substring} is a subsequence of $\tau$, $(\tau_i, \ldots, \tau_j)$, for some $1 \leq i < j\leq n$, and \textit{reversing} this substring yields $(\tau_j, \tau_{j-1}, \ldots, \tau_i)$. A \textit{substring reversal} of $\tau$ is any permutation obtained from $\tau$ by reversing a substring in $\tau$. Substring reversal is a well-studied operation on permutations, and often appears in metrics on permutations, edit distances and permutation statistics. There are numerous applications involving many variations of substring reversal, such as genome arrangements and sequencing (see \cite{BafnaPevzner1996}, \cite{Hannenhalli1996}, \cite{ks}). The \textit{reversal graph} $R_n$ is the graph whose vertex set is the permutation group $S_n$, where two vertices are adjacent if they are substring reversals of each other. Thus, $R_n$ has $n!$ vertices and is regular with degree $\binom {n} 2$. Many properties of the reversal graph $R_n$ have long been studied. One interesting problem is to determine the minimum number of substring reversals needed to transform one given permutation in $S_n$ to another, which is equivalent to finding a shortest path in $R_n$. The smallest number of reversals required to turn any permutation into any other is exactly the diameter of $R_n$, and it was shown in \cite{BafnaPevzner1996} that the diameter of the reversal graph is exactly $n-1$. The connectivity and hamiltonicity of $R_n$ were investigated in \cite{LiMeng2008}. There are still many questions concerning $R_n$ that remain unresolved. In this paper, we examine the eigenvalues of $R_n$, and determine the second largest eigenvalue of the adjacency matrix of $R_n$. Note that the second largest adjacency eigenvalue of a regular graph is intimately related to the rate of convergence for random walks on a graph. We use methods from graph coverings to determine the second largest eigenvalue of $R_n$, although our techniques cannot be used to determine the whole spectrum of $R_n$. An intriguing variation of substring reversal is {\it prefix reversal} (or {\it pancake flipping}) where only substrings of the form $(\tau_1, \ldots, \tau_j)$ are allowed to be reversed. The \textit{prefix reversal graph}, or the \textit{pancake graph}, $\mathcal{P}_n$ is a special subgraph of $R_n$. ${\mathcal P}_n$ also has vertex set $S_n$ but the edge set is restricted. In $\mathcal{P}_n$, the neighbors of $\tau$ are the permutations of the form \[ (\tau_k, \tau_{k-1}, \cdots, \tau_1, \tau_{k+1}, \cdots, \tau_n) \] for $1 < k \leq n$. In contrast to the reversal graph where the exact value of the diameter is known, the problem of determining the diameter of the pancake graph has a long history and still remains open. This problem was first posed by Jacob Goodman, under the pseudonym Harry Dweighter, as a Monthly problem in 1975 \cite{AMM}. If we denote the diameter of the pancake graph on $n$ vertices by $f(n)$, then the current best upper bound is $f(n) \leq \frac{18}{11} n $, due to Chitturi et al. \cite{Chitturi2009}, improving on a previous bound of $\frac{5}{3} n$ given by Gates and Papadimitriou \cite{Gates1979} in 1979. The best lower bound is $f(n) \geq 15 \left\lfloor \frac{n}{14} \right\rceil$, which is due to Heydari and Sudborough \cite{HeydariSudborough}. Recently it was shown that the problem of determining the exact minimum number of flips to transform one permutation $\tau_1$ into another permutation $\tau_2$, for two given permutations $\tau_1$ and $\tau_2$, is NP--hard \cite{Bulteau2015}. In \cite{Cesi2009}, it was determined that the spectral gap of $\mathcal{P}_n$ is one, answering a question posed in \cite{GunnellsEtAl2007}. We will determine the spectral gaps for a family of graphs which contains certain Cayley graphs including $\mathcal{P}_n$, giving an alternative proof in that case. We then use the spectral gap of $\mathcal{P}_n$, together with a decomposition of $R_n$ into $P_n$ and copies of $R_{n-1}$, to determine the second largest eigenvalue of $R_n$. \begin{theorem}\label{thm:rev_eig} If $\mu_1, \mu_2$ are the two largest eigenvalues of the adjacency matrix of $R_n$, then \[ \mu_1 = \binom{n}{2}, \text{ and } \mu_2 = \binom{n}{2}-n. \] \end{theorem} We will consider a family of graphs that generalizes the pancake graph, and show that for every graph in this family the spectral gap is one. \begin{theorem}\label{thm:main} Let $\mathcal{F}_n$ be the set of all graphs whose vertex set is the symmetric group $S_n$, and where for each vertex $\tau$ and each $2 \leq i \leq n$, $\tau$ is adjacent to exactly one vertex of the form \[ (\tau_i, \alpha_2, \alpha_3, \cdots, \alpha_{i-1}, \tau_1, \tau_{i+1}, \cdots, \tau_n). \] That is, the first and $i$th entries are swapped, and the entries in between are possibly rearranged. Then for any graph $G \in \mathcal{F}_n$, the two largest eigenvalues of the adjacency matrix of $G$ are $n-1$ and $n-2$. In particular, the adjacency spectral gap of $G$ is $1$. \end{theorem} The graphs $R_n$ and $\mathcal{P}_n$, as well as many of the graphs in $\mathcal{F}_n$, are Cayley graphs of the symmetric group $S_n$. Indeed, Cayley graphs of the symmetric group have been the subject of extensive study, with particular interest in their spectral gap. In \cite{Lubotzky}, Lubotzky posed the problem of finding a family of $k$-regular Cayley graphs of $S_n$ with spectral gap bounded away from zero; an explicit construction of such a family was found in \cite{Kassabov2005}. For many particular Cayley graphs of $S_n$, the spectral gap has been computed \cite{Friedman2000,FlattoEtAl1985,Cesi2009}, and the case when $S$ consists of transpositions is particularly well-studied. Of particular relevance here, the Cayley graph with generating set \[S = \{(1\ k) : 2 \leq k \leq n\}\] belongs to the family $\mathcal{F}_n$, and the spectral gap was determined to be $1$ in \cite{FlattoEtAl1985}. The remainder of the paper is organized as follows. In Section 2 we review the necessary background and establish notation. In Section 3 we recall the notions of graph coverings and projections, which we will use frequently in our proofs. In Section 4 we introduce a graph which is a projection of every graph in the family $\mathcal{F}_n$, which provides a lower bound of one on the spectral gap of every graph in this family. We establish the corresponding upper bound in Section 5. In Section 6 we prove Theorem~\ref{thm:rev_eig} and further investigate the spectrum of $R_n$. We conclude with some problems and remarks. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% SECTION TWO %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} Before proceeding to define the graph spectra of interest here, we note that the definitions of eigenvalues and eigenvectors are much simpler and cleaner for regular graphs than those of weighted irregular graphs. Although the graphs $R_n$ and the graphs in $\mathcal{F}_n$, are regular, we will consider various associated graphs which are irregular and weighted in order to determine the spectral gap that we need. Furthermore, we remark that the spectral gap of the adjacency matrix of a weighted or unweighted graph often depends on a few of the largest degrees and therefore the spectral gap of the adjacency matrix can {\it not} be used to determine the rate of convergence for random walks on irregular graphs. Instead it is more appropriate to study the combinatorial Laplacian and normalized Laplacian. In this section, we consider general weighted graphs and define the eigenvalues of the normalized Laplacian, which will be important when we define graph covers. For undefined terminology, the reader is referred to \cite{cgn}. %We will use the following standard result from matrix analysis, see for %example \cite{HornJohnson}. %\begin{theorem}[Rayleigh--Ritz]\label{rayleigh} %If $M$ is a Hermitian matrix, then the $k$th largest eigenvalue satisfies % \[ \mu_k(M) = \max_{\textbf{v} \perp V_{k-1}} \frac{\textbf{v}^t M \textbf{v}}{\textbf{v}^t \textbf{v}}\] %where $V_{k-1}$ is the vector space generated by $k-1$ eigenvectors %corresponding to the largest $k-1$ eigenvalues, and $V_0 = \emptyset$. %\end{theorem} Let $G$ denote a weighted undirected graph with edge weight $w_{u,v} = w_{v,u}$. The adjacency matrix of $G$, denoted by $A_G$, has entries $A_G(u,v)= w_{u,v}$ for vertices $u$ and $v$. For any vertex $v \in V(G)$, the set of vertices adjacent to $v$ is denoted by $N(v)$. The degree $d_v$ of a vertex $v$ is defined to be \[ d_v = \sum_u w_{u,v}. \] We will only consider weighted graphs without isolated vertices, i.e., $d_v > 0$ for all $v$. Let $D_G$ be the diagonal degree matrix whose $i$th diagonal entry is equal to the degree of the $i$th vertex. Then the combinatorial Laplacian of $G$ is $L_G = D_G - A_G$, and the normalized Laplacian is $\mathcal{L}_G = D_G^{-1/2} L_G D_G^{-1/2}$. For a $d$-regular graph, we have $\mathcal{L}_G =1 - \frac{1}{d} A_G$. The eigenvalues of the normalized Laplacian $\mathcal{L}_G$ are denoted by $0=\lambda_0 \leq \lambda_1 \leq \ldots \leq \lambda_{n-1}$ where $n$ is the number of vertices in $G$. $\lambda_1$ is called the spectral gap of the normalized Laplacian, and the rate of convergence of random walks on $G$ with transition probability matrix $P=D_G^{-1} A_G$ is exactly $ \lambda_1^{-1}$ (see \cite{cgn}). We will denote the eigenvalues of the adjacency matrix of $G$ by $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_n$, and $\mu_1 - \mu_2$ is the spectral gap of the adjacency matrix. For a regular graph of degree $d$, $\mu_1=d$ and $\mu_2 = d (1-\lambda_1)$. Let $\phi_i$ denote the orthonormal eigenvector associated with $\lambda_i$. It can easily be shown that $\phi_0 = D_G^{1/2}/\sqrt{\vol(G)}$ where $\vol(G)=\sum_v d_v$. %From the %Rayleigh--Ritz Theorem, we have %\begin{align*} %\lambda_1&= \inf_{g \perp \phi_0} \frac{ \langle g, \mathcal{L}_G g \rangle}{\langle g, g \rangle}\\ %&= \inf_{f \perp D_G \mathbf{1}} \frac{ \langle f, {L}_G f \rangle}{\langle f, D_G f \rangle}\\ %&= \inf_{f \perp D_G \mathbf{1}} \frac{\sum_{x \sim y} (f(x)-f(y))^2w_{x,y}}{\sum_x f^2(x) d_x} %\end{align*} Instead of dealing with eigenvectors $\phi_i$ of $\mathcal{L}_G$, it is often convenient to consider the corresponding \textit{harmonic eigenfunction} defined by $f_i = D_G^{-1/2} \phi_i$ which satisfies \[ \lambda_i f_i(u)d_u= \sum_{v} w_{u,v} (f(u)-f(v)) \] for all vertices $u$. Note that for regular graphs, harmonic eigenfunctions are exactly eigenfunctions. Moreover, for regular graphs the eigenfunctions of $\mathcal{L}, L$ and $A$ are the same, and the corresponding spectra are translations of each other. We will frequently deal with permutations, so we establish the notation that we will use. The symmetric group is denoted as $S_n$ throughout. Every permutation will be given in \textit{word notation}, that is, as a list of numbers $(\tau_1, \tau_2, \cdots, \tau_n)$, which indicates that permutation $\tau$ maps $i$ to $\tau_i$. We will sometimes refer to the value $\tau_i$ as the $i$th \textit{entry} or \textit{position} of the permutation $\tau$. When we write the product of two permutations, such as $\pi \sigma$, we take this to mean: first apply permutation $\sigma$, then apply permutation $\pi$. As discussed in Section~1, $R_n$ and many of the graphs in the family $\mathcal{F}_n$ are Cayley graphs. We briefly recall the definition here. Let $H$ be a finite group, and $S$ a subset of $H$. We say that $S$ is a symmetric set if whenever $s \in S$, we also have $s^{-1} \in S$. Given a symmetric set $S$ that generates the group $H$, the right-Cayley graph $\text{Cay}_R(H,S)$ is the graph with vertex set equal to $H$, and edges of the form $\{x, xs\}$ for all $x \in H, s \in S$. This is an undirected $|S|$-regular graph. A left-Cayley graph is defined similarly, with edges of the form $\{x,sx\}$. For example, let $S$ be the set of permutations corresponding to substring reversals. That is, $S$ consists of the permutations obtained from taking the identity permutation $(1, 2, 3, \cdots, n)$ and reversing a substring. Then $R_n = \text{Cay}_R(S_n,S)$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% SECTION THREE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Graph coverings} In proving Theorem~\ref{thm:main} and Theorem~\ref{thm:rev_eig}, we will rely heavily on graph coverings, an idea developed in \cite{coverings}. A short overview is presented here. Let $G$ and $ \tilde{G}$ be two weighted graphs. Then $\tilde{G}$ is a \textit{covering} of $G$ if there is a surjection $\pi : V(\tilde{G}) \to V(G)$ satisfying the following two properties: \begin{itemize} \item[(1)] For $x,y \in V(\tilde{G})$, where $\pi(x) = \pi(y)$, and for any $v \in V(G)$ \[ \displaystyle \sum_{z \in \pi^{-1}(v)} w(z,x) = \displaystyle \sum_{z \in \pi^{-1}(v)} w(z,y) . \] \item[(2)] There is a fixed $m \in \mathbb{R}^{+} \cup \{\infty\}$, the \textit{index} of $\pi$, such that for all $u,v \in V(G)$ \begin{equation}\label{covering_sum_condition} \displaystyle \sum_{\substack{x \in \pi^{-1}(u) \\ y \in \pi^{-1}(v)}} w(x,y) = m w(u,v) . \end{equation} \end{itemize} As $\pi$ is a surjection, it can alternatively be viewed as a partition of the vertices of $V(\tilde{G})$ into $|V(G)|$ sets. With this interpretation, the above definition can be seen as a generalization of an \textit{equitable partition}; see, for example, \cite{agt}. We say that $G$ is a {\it projection} of $\tilde{G}$ via the mapping $\pi$ if $\tilde{G}$ is a covering of $G$ under $\pi$. The virtue of a graph covering is that there is a strong correspondence between the eigenvalues of a covering graph and the eigenvalues of the projection. This correspondence is the content of the following theorem, which is proved in \cite{coverings}. \begin{theorem}\label{thm:cov-cor} \emph{(Covering-Correspondence)} \\ Let $G, \tilde{G}$ be two weighted undirected graphs, and $\pi : V(\tilde{G}) \to V(G)$ be a covering map. For any function $f : V(\tilde{G}) \to \mathbb{C}$, define $p_f : V(G) \to \mathbb{C}$ by \[ p_f(v) = \displaystyle \sum_{x \in \pi^{-1}(v)} \frac{f(x) d_x}{d_v} . \] For any function $f : V(G) \to \mathbb{C}$, define the \textit{lift} of $f$, $l_f : V(\tilde{G}) \to \mathbb{C}$ by \[ l_f(x) = f(u), \text{ where $\pi(x) = u$}. \] \begin{itemize} \item[(i)] If $\lambda$ is an eigenvalue of $G$ with harmonic eigenfunction $f$, then $\lambda$ is an eigenvalue of $\tilde{G}$ with harmonic eigenfunction $l_f$. \item[(ii)] If $\lambda$ is an eigenvalue of $\tilde{G}$ with harmonic eigenfunction $f$, then if $p_f \neq 0$, $\lambda$ is an eigenvalue of $G$ with harmonic eigenfunction $p_f$. \end{itemize} \end{theorem} We will use this theorem in the form of the following corollary. \begin{corollary}\label{cor:cov-cor} Let $G$ be a graph with cover $\tilde{G}$, under covering map $\pi$, where $\tilde{G}$ is a regular graph. Then the eigenvalues of the normalized Laplacian of $G$ are eigenvalues of the normalized Laplacian of $\tilde{G}$. For any eigenvalue $\lambda$ of the normalized Laplacian of $\tilde{G}$ that is not an eigenvalue of $G$, the corresponding eigenfunction $f$ satisfies \begin{equation}\label{eqn:sum_to_zero} \sum_{x \in \pi^{-1}(u)} f(x) = 0 \end{equation} for all $u \in V(G)$. Furthermore, if $G$, $\tilde{G}$ are both regular graphs with the same degree $d$, then this holds for their adjacency matrices as well. %Suppose $\tilde{G}$ is a %cover of $G$ and $f$ is an eigenvector associated an eigenvalue $\lambda$ of $\tilde{G}$. %If $\lambda$ is not an eigenvalue of $G$, then $f$ satisfies %for every vertex $u $ of $ G$. \end{corollary} \begin{proof} It follows directly from Theorem~\ref{thm:cov-cor} that if $\lambda$ is an eigenvalue of the normalized Laplacian of $G$, then it is an eigenvalue of $\tilde{G}$. Now let $\lambda$ be an eigenvalue of $\tilde{G}$ with eigenfunction $f$, where $\lambda$ is not an eigenvalue of $G$. By regularity of $\tilde{G}$, $f$ is also a harmonic eigenfunction, and by part (ii) of Theorem~\ref{thm:cov-cor} it must be the case that $p_f = 0$. Hence, for all $u \in V(G)$, \[ 0 = p_f(u) = \displaystyle \frac{1}{d_u} \sum_{x \in \pi^{-1}(u)} f(x) d_x .\] By regularity, $d_x$ is constant, and so dividing by a constant gives equation~\ref{eqn:sum_to_zero}. If $G$, $\tilde{G}$ are both $d$-regular graphs, then their adjacency eigenvalues satisfy $\mu_i = d(1-\lambda_{i-1})$, and the corresponding eigenfunctions are the same. It follows that adjacency eigenvalues of $G$ are also adjacency eigenvalues of $\tilde{G}$, and for any other adjacency eigenvalue of $\tilde{G}$ the corresponding eigenfunction satisfies equation~\ref{eqn:sum_to_zero}. \end{proof} \vspace*{1mm} \noindent \textbf{Example.} Let $G$ be the Petersen graph. We compute the eigenvalues of $G$ by finding a graph $G'$ for which $G$ is a cover. Define $G'$ to be the weighted graph with vertex set $\left\{ v_1, v_2, v_3\right\}$, and edges and edge weights as shown in Figure~\ref{petersen}. The adjacency matrix and normalized Laplacian of $G'$ are \[ A_{G'} = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 4 \end{bmatrix}, \mathcal{L}_{G'} = \begin{bmatrix} 1 & -\frac{1}{\sqrt{3}} & 0 \\ -\frac{1}{\sqrt{3}} & 1 & -\frac{\sqrt{2}}{3} \\ 0 & -\frac{\sqrt{2}}{3} & \frac{1}{3} \end{bmatrix} \] Now fix any vertex $x \in V(G)$, and define a map $\pi : V(G) \to V(G')$ by \[ \pi(y) = \begin{cases} v_1 & y = x \\ v_2 & y \sim x \\ v_3 & \text{otherwise} \end{cases} \] It is easy to check that $\pi$ satisfies the definition of a graph covering (with index $m=3$), and so the eigenvalues of $\mathcal{L}_{G'}$, which are $0, \frac{2}{3}, \frac{5}{3}$, are eigenvalues of $\mathcal{L}_G$. \noindent Furthermore these must be the only eigenvalues of $\mathcal{L}_G$. Otherwise, let $f$ be a harmonic eigenfunction corresponding to some other eigenvalue. By vertex transitivity of $G$, we can assume $f(x) \neq 0$. By the covering-correspondence theorem, since $f$ does not correspond to an eigenvalue of $G'$ we have that $p_f = 0$. Hence \[ 0 = p_f(v_1) = \sum_{y \in \pi^{-1}(v_1)} f(y) \frac{d_y}{d_{v_1}} = f(x) d_x \] since by construction of $\pi$, $x$ is the only vertex mapped to $v_1$. It follows that $f(x)=0$ which is a contradiction, and this shows that all of the eigenvalues of $\mathcal{L}_{G}$ are eigenvalues of $\mathcal{L}_{G'}$. \begin{figure}[ht] \begin{subfigure}{.49\textwidth} \centering \begin{tikzpicture} \coordinate (center) at (1,2); \def\radius{.75cm} \def\rad2{1.5cm} \coordinate (o0) at (0*360/5+90:\radius); \coordinate (o1) at (1*360/5+90:\radius); \coordinate (o2) at (2*360/5+90:\radius); \coordinate (o3) at (3*360/5+90:\radius); \coordinate (o4) at (4*360/5+90:\radius); \coordinate (i0) at (0*360/5+90:\rad2); \coordinate (i1) at (1*360/5+90:\rad2); \coordinate (i2) at (2*360/5+90:\rad2); \coordinate (i3) at (3*360/5+90:\rad2); \coordinate (i4) at (4*360/5+90:\rad2); \draw (i0) -- (i1); \draw (i1) -- (i2); \draw (i2) -- (i3); \draw (i3) -- (i4); \draw (i4) -- (i0); \draw (o0) -- (o2); \draw (o0) -- (o3); \draw (o1) -- (o3); \draw (o1) -- (o4); \draw (o2) -- (o4); \draw (i0) -- (o0); \draw (i1) -- (o1); \draw (i2) -- (o2); \draw (i3) -- (o3); \draw (i4) -- (o4); \fill[cyan] (center) (o0) circle[radius=3pt]; \fill[red] (center) (o1) circle[radius=3pt]; \fill[red] (center) (o2) circle[radius=3pt]; \fill[red] (center) (o3) circle[radius=3pt]; \fill[red] (center) (o4) circle[radius=3pt]; \fill[black] (center) (i0) circle[radius=3pt]; \fill[cyan] (center) (i1) circle[radius=3pt]; \fill[red] (center) (i2) circle[radius=3pt]; \fill[red] (center) (i3) circle[radius=3pt]; \fill[cyan] (center) (i4) circle[radius=3pt]; \end{tikzpicture} \caption{Petersen graph $G$} %\label{petersen} \end{subfigure} \begin{subfigure}{.5\textwidth} \centering \begin{tikzpicture} \coordinate (v1) at (0,-0.5); \coordinate (v2) at (1.5,-0.5); \coordinate (v3) at (3,-0.5); \coordinate (v3_eps) at (3.25,-0.5); \coordinate (loop_label) at (3.65,-0.2); \draw (v1) node[below] {$v_1$}; \draw (v2) node[below] {$v_2$}; \draw (v3) node[below] {$v_3$}; \draw (v1) -- node[above]{1} (v2); \draw (v2) -- node[above]{2} (v3); \draw (loop_label) node {4}; \draw[black] (v3_eps) circle[radius=6pt]; \filldraw[white] (0,1.05) circle[radius=3pt]; \filldraw[white] (0,-2.1) circle[radius=3pt]; \filldraw[black] (v1) circle[radius=3pt]; \filldraw[cyan] (v2) circle[radius=3pt]; \filldraw[red] (v3) circle[radius=3pt]; % \[red] (cyan) (o3) circle[radius=3pt]; % \fill[red] (red) (o3) circle[radius=3pt]; \end{tikzpicture} \caption{Graph $G'$} \label{petersen_a} \end{subfigure} \caption{The Petersen graph $G$ and a three vertex weighted graph which it covers. In the covering map, vertices in $G$ are sent to the vertex with same color in $G'$.\label{petersen}} \end{figure} % NOTE(Josh): Can use this later % \noindent \textbf{Example.} Consider an even cycle $C_{2n}$, and let $P_{n+1}$ % be the path of length $n+1$. Then $P_{n+1}$ is a projection of $C_{2n}$. We % construct the covering map $\pi$ as follows. % % % Let $d(x,y)$ % be the length of a shortest path from vertex $x$ to vertex $y$ in $C_{2n}$. % Denote the vertices of the path by $v_0, v_1, \cdots, v_{n}$, where $v_i$ % is adjacent to $v_{i+1}$. % Now for any fixed vertex $x$ in $C_{2n}$, we can define the map % $\pi : V(C_{2n}) \to V(P_{n+1})$, where $\pi$ sends vertex $y$ to the % vertex $v_{d(y,x)}$. This is a covering map with index $m=2$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% SECTION FOUR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{A projection of graphs in $\mathcal{F}_n$} We begin by constructing a weighted graph $G_n$ on three vertices, which is a projection of every graph in $\mathcal{F}_n$. Then we compute the eigenvalues of $G_n$, and by Corollary~\ref{cor:cov-cor}, these will be eigenvalues of every graph in $\mathcal{F}_n$. Let $F$ be a graph in $\mathcal{F}_n$, and let $G_n$ be the weighted graph with vertices $\{v_1, v_2, v_3\}$, with edge weights $w(v_1,v_1) = n-2$, $w(v_1,v_2) = 1$, $w(v_2, v_3) = n-2$, $w(v_3,v_3) = (n-2)^2$, and all other edge weights zero. To construct the covering map $\pi : V(F) \to V(G_n)$, we just need to specify the sets $U_1 = \pi^{-1}(v_1), U_2 = \pi^{-1}(v_2), U_3 = \pi^{-1}(v_3)$: \begin{eqnarray*} U_1 = \pi^{-1}(v_1) & = & \{\tau \in S_n : \tau_n = n \} \\ U_2 = \pi^{-1}(v_2) & = & \{\tau \in S_n : \tau_1 = n \} \\ U_3 = \pi^{-1}(v_3) & = & \{\tau \in S_n : \tau_1 \neq n, \tau_n \neq n \} \end{eqnarray*} \noindent In order to verify that this is a covering, we need to check the two properties: \begin{itemize} \item[(1)] We need to show that any two vertices in the same preimage set $U_i$ have the same number of neighbors in each preimage set $U_j$. For example, take $\tau \in U_3$, so $\tau_k = n$ for some $1 < k < n$. By definition of $\mathcal{F}_n$, if $\sigma$ is adjacent to $\tau$ then either $\sigma_n = \tau_n$ or $\sigma_n = \tau_1$. In particular, $\sigma_n \neq n$, so $\tau$ is not adjacent to any vertex in $U_1$. There is exactly one neighbor of $\tau$ with $\sigma_1 = n$, and so $\tau$ is adjacent to exactly one vertex in $U_1$. The remaining $n-2$ neighbors of $\tau$ are in $U_3$. As required, the number of neighbors in each preimage set did not depend on the choice of $\tau \in U_3$. The cases that $\tau \in U_1$ and $\tau \in U_2$ are similar. \item[(2)] We need to verify equation~\ref{covering_sum_condition} for each pair chosen from the preimage sets $U_1, U_2, U_3$. For this covering, we have $m=(n-1)!$. Firstly, $U_1$ and $U_1$: \[ \sum_{\substack{x \in U_1 \\ y \in U_1}} w(x,y) = \sum_{x \in U_1} (n-2)\] since each element of $U_1$ is adjacent to exactly $n-2$ elements in $U_1$. So \[ \sum_{\substack{x \in U_1 \\ y \in U_1}} w(x,y) = |U_1| (n-2) = (n-1)! w(v_1,v_1)\] as required. The pairs $U_1$, $U_2$ and $U_2$, $U_3$ are similarly verified. % Next, $U_1$ and $U_2$: % \[ \sum_{\substack{x \in U_1 \\ y \in U_2}} w(x,y) = \sum_{x \in U_1} 1 = (n-1)! w(v_1, v_2) .\] For the pair $U_1$ and $U_3$, since there are no edges between these sets and since $w(v_1,v_3) = 0$, we are done. Similarly for the pair $U_2$ and $U_2$. %For $U_2$ and $U_3$ we have %\[\sum_{\substack{x \in U_2 \\ y \in U_3}} w(x,y) = \sum_{x \in U_1} (n-2) = (n-1)! w(v_2, v_3) . \] And finally, the pair $U_3, U_3$: \[\sum_{\substack{x \in U_3 \\ y \in U_3}} w(x,y) = \sum_{x \in U_3} (n-2) = |U_3|(n-2)\] Now $|U_3| = n! - |U_1| - |U_2| = (n-2) (n-1)!$, so we get \[\sum_{\substack{x \in U_3 \\ y \in U_3}} w(x,y) = (n-1)! w(v_3,v_3)\] as required. \end{itemize} Now that we have a covering, we evaluate the eigenvalues of the projection $G_n$. \begin{lemma} \label{g_eigen} The eigenvalues of the normalized Laplacian of $G_n$ are \\$0, \frac 1{n-1}, \frac n {n-1}$. \end{lemma} \begin{proof} % The adjacency matrix of $G_n$ is % \[ \left[ \begin{array}{ccc} n-2 & 1 & 0\\ % 1 & 0 & n-2 \\ % 0 & n-2 & (n-2)^2 % \end{array} \right] \] The normalized Laplacian of $G_n$ is \[ \left[ \begin{array}{ccc} \frac 1 {n-1} &- \frac 1 {n-1} & 0\\ - \frac 1 {n-1} &1 &- \frac{\sqrt{n-2}}{n-1} \\ 0 & -\frac{\sqrt{n-2}}{n-1} & \frac 1 {n-1} \end{array} \right] \] The result follows from a simple computation. \end{proof} \begin{corollary}\label{cor:adj_spec} For any $G \in \mathcal{F}_n$, the adjacency matrix $A_{G}$ has eigenvalues $n-1$, $n-2$ and $-1$. For $1 \leq i \leq n$ define \begin{eqnarray*} X(i) & = & \{\tau \in S_n : \tau_n = i \} \\ Y(i) & = & \{\tau \in S_n : \tau_1 = i \} \\ Z(i) & = & \{\tau \in S_n : \tau_1 \neq i, \tau_n \neq i \} \end{eqnarray*} Then any eigenfunction corresponding to any other eigenvalue than those listed above must sum to zero on each of $X(i)$, $Y(i)$ and $Z(i)$, for any $i \in \{1,2,\cdots,n\}$. \end{corollary} \begin{proof} When defining the covering mapping $\pi$ to $G_n$, for a permutation $\tau$ the vertex it was mapped to was determined by the position of $n$ in $\tau$. Observe that we can replace $n$ with any index $i$, $1 \leq i \leq n$, and we still have a covering, in this case with preimage sets $X(i)$, $Y(i)$, $Z(i)$. Now take an eigenfunction of $G$ which corresponds to an eigenfunction other than $n-1$, $n-2$, or $-1$. $G$ is regular, so this eigenfunction is also an eigenfunction of the normalized Laplacian of $G$, corresponding to an eigenvalue other than $0$, $1/(n-1)$ or $n/(n-1)$. It follows from Corollary~\ref{cor:cov-cor} and the previous lemma that the eigenfunction must sum to zero over the preimage sets of the covering, which are $X(i)$, $Y(i)$ and $Z(i)$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% SECTION FIVE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Spectral gap of graphs in $\mathcal{F}_n$} Recall that $\mathcal{F}_n$ is the family of graphs whose vertex set is $S_n$ and where for each vertex $\tau$, \[ \tau = (\tau_1, \tau_2, \cdots, \tau_n), \] and each $2 \leq i \leq n$, $\tau$ is adjacent to exactly one vertex of the form \[ (\tau_i, \alpha_2, \alpha_3, \cdots, \alpha_{i-1}, \tau_1, \tau_{i+1}, \cdots, \tau_n). \] Each graph in $\mathcal{F}_n$ is an $(n-1)$-regular graph. The prefix reversal graph $\mathcal{P}_n$ is in $\mathcal{F}_n$, as well as the right-Cayley graph generated by the transpositions $(1\ k)$, where $2 \leq k \leq n$. In order to compute the spectral gap of graphs in $\mathcal{F}_n$, we proceed by induction, so first we compute the spectrum of graphs in $\mathcal{F}_3$ to establish our base case. \begin{lemma}\label{base_case} $\mathcal{F}_3 = \{ C_6 \}$. In particular, the adjacency spectral gap of every graph in $\mathcal{F}_3$ is one. \end{lemma} \begin{proof} Let $G \in \mathcal{F}_3$. Then $G$ is a $2$-regular graph on $3! = 6$ vertices. From the definition of $\mathcal{F}_3$, it is easy to verify that $G$ is connected, and so $G = C_6$. The first two adjacency eigenvalues of $C_6$ are $2$ and $1$. \end{proof} %\begin{theorem} % For $n \geq 3$, and any $G \in \mathbb{P}_n$, the spectral gap of $\mathcal{L}_{G}$ is $1/(n-1)$, and the spectral % gap of $A_{G}$ is $1$. We can now prove the theorem on the spectral gap of ${\mathcal F}_n$, as stated in the Section~1. %\end{theorem} \begin{proof}[Proof of Theorem~\ref{thm:main}] We proceed by induction, so assume that the adjacency spectral gap of any graph in $\mathcal{F}_{n-1}$ is $1$. The base case is established by Lemma~\ref{base_case}. By $(n-2)$-regularity of graphs in $\mathcal{F}_{n-1}$, it follows from the inductive assumption that the second largest eigenvalue of any graph in $\mathcal{F}_{n-1}$ is $n-3$. Let $G$ be a graph in $\mathcal{F}_{n}$. Pick any eigenvector $f$ coming from an eigenvalue $\mu$ that is not $n-1$, $n-2$ or $-1$. Our goal is to show that $\mu < n-2$. Recall that $X(i)$ consists of the permutations whose last entry is $i$, $Y(i)$ consists of the permutations whose first entry is $i$ and $Z(i)$ consists of all other permutations. For any $i$, from Corollary~\ref{cor:adj_spec} we get a projection of $G$ with preimage sets $X(i), Y(i), Z(i)$. The set $X(i)$ induces a graph in $\mathcal{F}_{n-1}$, and the set $Y(i)$ induces an independent set (since every two adjacent permutations have different first entries). Furthermore the edges between $X(i)$ and $Y(i)$ form a matching. Our proof strategy is the following: we will get an expression for $\mu$ involving the values of $f$ on the set $X(i)$ and the set $Y(i)$. We can control the contribution from $X(i)$ using the inductive assumption, and then we show that we can choose $i$ so that the contribution from $Y(i)$ is small enough to yield the stated result. \vspace*{1mm} \begin{claim}\label{claim:f_choice} We can fix an $i$ such that \begin{equation}\label{eqn:gap_max} \sum_{x \in X(i)} f(x)^2 \geq \sum_{y \in Y(i)} f(y)^2 \end{equation} and \[ \sum_{x \in X(i)} f(x)^2 > 0. \] \end{claim} \begin{proof}[Proof of claim] Notice that the sets $X(1), X(2), \cdots, X(n)$ partition the vertex set of $G$ (ie. partitioning the permutations based on the last entry). Similarly, the sets \\ $Y(1), Y(2), \cdots, Y(n)$ partition the vertex set of $G$. Hence \[ \sum_{j=1}^n \sum_{x \in X(j)} f(x)^2 = \sum_{j=1}^n \sum_{y \in Y(j)} f(y)^2 >0 . \] In particular, there exists an index $i$ such that \begin{equation*} \sum_{x \in X(i)} f(x)^2 \geq \sum_{y \in Y(i)} f(y)^2. \end{equation*} Let $I$ denote the set of indices $i$ satisfying the above inequality. Then there exists some $i$ in $I$ satisfying \begin{equation*} \sum_{x \in X(i)} f(x)^2 > 0 \end{equation*} since $f \not = 0$. \end{proof} Consider an arbitrary vertex $x \in X(i)$. Then by definition of $X(i)$, $x$ is a permutation with $x(n) = i$. $x$ has $n-1$ neighbors in $G$, $n-2$ of these neighbors are in $X(i)$ and one of its neighbors is in $Y(i)$. Let $c_x$ be the unique neighbor of $x$ in $Y(i)$. As noted above, the induced subgraph on $X(i)$ is in $\mathcal{F}_{n-1}$. By the eigenvalue-eigenvector equation, we have \[ \mu f(x) = f(c_x) + \sum_{y \in N(x) \cap X(i)} f(y) .\] Multiplying both sides by $f(x)$, and summing over $x \in X(i)$ yields \[ \mu \sum_{x \in X(i)} f(x)^2 = \sum_{x \in X(i)} f(x) f(c_x) + \sum_{x \in X(i)} \sum_{y \in N(x) \cap X(i)} f(x) f(y) .\] Dividing across by the sum on the left-hand side (which is non-zero by Claim~\ref{claim:f_choice}) gives \begin{equation}\label{eqn:gap_to_bound} \mu = \frac{\sum_{x \in X(i)} f(x) f(c_x)}{\sum_{x \in X(i)} f(x)^2} + \frac{\sum_{x \in X(i)} \sum_{y \in N(x) \cap X(i)} f(x) f(y)}{\sum_{x \in X(i)} f(x)^2} . \end{equation} We will now find upper bounds for each of the two terms on the right-hand side. Let ${G'}$ be the induced subgraph on $X(i)$, which is a graph in $\mathcal{F}_{n-1}$, and let $g = f|_{X(i)}$. Since $\sum_{x \in X(i)} f(x)=0$, we have that $g \perp \textbf{1}$, where $\textbf{1}$ is the constant vector with entries $1$, which is the eigenvector associated with $\mu_1$. Now we can bound the second term in equation~\ref{eqn:gap_to_bound} by $n-3$: \begin{eqnarray*} \displaystyle \frac{\displaystyle\sum_{x \in X(i)} \displaystyle\sum_{y \in N(x) \cap X(i)} f(x) f(y)}{\displaystyle\sum_{x \in X(i)} f(x)^2} & = & \frac{g^T A_{G'} g}{ g^T g} \\ &\leq& \text{max}_{h \perp \textbf{1}} \frac{h^T A_{G'} h}{h^T h} \\ &=& \mu_2(G') \\ &=& n-3. \end{eqnarray*} The edges between $X(i)$ and $Y(i)$ are a matching. So as $x$ ranges over the vertices of $X(i)$, $c_x$ ranges over the vertices of $Y(i)$. By Cauchy--Schwarz, \begin{eqnarray*} \sum_{x \in X(i)}f(x) f(c_x) & \leq & \sqrt{\sum_{x \in X(i)}f(x)^2 \sum_{x \in X(i)}f(c_x)^2 } \\ & = & \sqrt{\sum_{x \in X(i)}f(x)^2 \sum_{y \in Y(i)}f(y)^2 } \end{eqnarray*} So \[ \frac{\displaystyle \sum_{x \in X(i)} f(x) f(c_x)}{\displaystyle \sum_{x \in X(i)} f(x)^2} \leq \sqrt{\frac{\displaystyle \sum_{y \in Y(i)}f(y)^2}{\displaystyle {\sum_{x \in X(i)}f(x)^2}}} \leq 1 \] where the last inequality follows from equation~\ref{eqn:gap_max}. Applying these two bounds in equation~\ref{eqn:gap_to_bound} gives \[ \mu \leq n-3 + 1 = n-2 . \] This shows that there is no eigenvalue of $G$ strictly between $n-2$ and $n-1$, so we conclude that $\mu_2(G) = n-2$. \end{proof} As a brief application of Theorem~\ref{thm:main}, we can establish bounds on the edge expansion of every graph in $G \in \mathcal{F}_n$. Recall that the edge expansion of a $d$-regular graph $G$, $h_G$, is defined as \[ h_G = \min_{S \subset V(G)} \frac{|E(S,\bar{S})|}{\min(|S|,|\bar{S}|) \cdot d} .\] If $S$ is the set of permutations whose last entry is $n$, then $|S| = |E(S,\bar{S})| = (n-1)!$, which gives the upper bound $h_G \leq 1/(n-1)$. To obtain a lower bound, we can use an inequality from \cite{cgn}, $h_G \geq \lambda_1 / 2$. Combining these two inequalities gives the bounds \[ \frac{1}{2(n-1)} \leq h_G \leq \frac{1}{n-1} .\] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% SECTION SIX %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Spectrum of the reversal graph}\label{s6} The graph $R_n$ is a Cayley graph of $S_n$ that does not belong to the family $\mathcal{F}_n$ but is closely related. For any $1 \leq i i$. The reversals that map $\tau$ into %$U(j)$ are exactly $r_{i,j}, r_{i-1,j+1}, r_{i-2,j+2}, \cdots$. It %follows that the number of vertices in $U(j)$ that are adjacent %to $\tau$ is $\text{min}\left\{i,j,n+1-i,n+1-j\right\}$. This is independent %of the vertex $\tau$ chosen. Similarly, we get the same total %when $j < i$. In particular any two vertices in $U(i)$ %have the same number of neighbors in $U(j)$, for any $j \neq i$. % %There are several types of reversals that map $\tau$ back into $U(i)$. They %are: the reversals $r_{j,k}$ where $j < k < i$, the reversals %$r_{j,k}$ where $i < j < k$, and finally the reversals of the form %$r_{i-k,i+k}$. Again, the number of such reversals does not depend on the %vertex $\tau$ chosen, and so any two vertices in $U(i)$ have the same number %of neighbors in $U(i)$. % % %It follows from the above two paragraphs that we can form a projection of %the graph $R_n$ on $n$ vertices, with preimage sets $U(i)$. The %adjacency matrix of this projection can be written as $D+X$, where % \[ X(i,j) = \text{min}\left\{i,j,n+1-i,n+1-j\right\} \] %and $D$ is the unique diagonal such that $D+X$ has constant row sum equal %to $\binom{n}{2}$. By Corollary~\ref{cor:cov-cor}, the eigenvalues %of $D+X$ are eigenvalues of $A_{R_n}$. The result then follows from %Lemma~\ref{lem:rev_eig}. \end{proof} We are finally ready to prove the main theorem determining the spectral gap of $R_n$. \noindent {\it Proof of Theorem \ref{thm:rev_eig}:} The value of $\mu_1$ is $\binom n 2$ since $R_n$ is regular of degree $\binom n 2$. From the previous lemma we have that \[ \mu_2 \geq \binom{n}{2} - n\] so it suffices to prove that \[ \mu_2 \leq \binom{n}{2} - n .\] We follow a similar approach to the proof of Theorem~\ref{thm:main}. We proceed by induction. For the base case, consider $n=2$. Then $R_2$ is $K_2$, with eigenvalues $1,-1$. Now assume for any $m < n$, we have \[ \mu_2(A_{R_m}) = \binom{m}{2} - m . \] For any $1 \leq i \leq n$, we define the sets \[ U_i(j) = \left\{ \tau \in S_n : \tau_j = i \right\}. \] As in the proof of Lemma~\ref{lem:rev_eig2}, for any fixed $i$ the sets $U_i(j)$, $1 \leq j \leq n$ are the preimages of a covering map of $R_n$, and the two largest eigenvalues of the projection are $\binom{n}{2}$ and $\binom{n}{2} - n$. It follows from Corollary~\ref{cor:cov-cor} that if $A_{R_n}$ has an eigenvalue $\mu$ strictly between $\binom{n}{2}$ and $\binom{n}{2} - n$ then the corresponding eigenvector must sum to zero on $U_i(j)$ for all $i,j$. Let $\mu$ be such an eigenvalue, with eigenvector $f$. Let $E_1 = \left\{ \left\{\sigma, \tau\right\} \in E(R_n) : \sigma_1 \neq \tau_1 \right\}$, that is, the set of edges arising from substring reversals that include the first entry of the permutation. Observe that the edge set $E_1$ is exactly the set of edges of the prefix reversal graph $\mathcal{P}_n$. Let $R'$ be the graph obtained by removing all edges in $E_1$ from $R_n$. Then $R'$ consists of $n$ connected components, $U_1(1), U_2(1), \cdots, U_n(1)$. Each of these connected components is isomorphic to $R_{n-1}$. We have, by the Rayleigh quotient \begin{eqnarray*} \mu & = & \frac{2\sum_{\{x,y\} \in E(R_n)} f(x) f(y)}{\sum_{x \in R_n} f(x)^2}\\ & = & \frac{2\sum_{\{x,y\} \in E_1} f(x) f(y)}{\sum_{x \in R_n} f(x)^2} + \frac{2\sum_{\{x,y\} \not \in E_1} f(x)f(y)}{\sum_{x \in R_n} f(x)^2}\\ & \leq & \mu_2(A_{\mathcal{P}_n}) + \frac{2\sum_{\{x,y\} \not \in E_1} f(x) f(y)}{\sum_{x \in R_n} f(x)^2} \end{eqnarray*} where the last inequality follows since $f$ is orthogonal to the constant vector $\textbf{1}$. Using Theorem~\ref{thm:main} we have $\mu_2(A_{\mathcal{P}_n}) = n-2$. To bound the second term, we will partition the edges not in $E_1$ in the following way \[ \left\{ \left\{ x,y \right\} \not \in E_1 \right\} = E(U_1(1)) \cup E(U_2(1)) \cup \cdots \cup E(U_n(1)) . \] Hence, we have \begin{eqnarray*} \frac{2\sum_{\{x,y\} \not \in E_1} f(x) f(y)}{\sum_{x \in R_n} f(x)^2} & = & \frac{\sum_{i=1}^n 2\sum_{\{x,y\} \in E(U_i(1))} f(x) f(y)}{\sum_{i=1}^n \sum_{x \in U_i(1)} f(x)^2} \\ & \leq & \text{max}_{1 \leq i \leq n} \frac{2\sum_{\{x,y\} \in E(U_i(1))} f(x) f(y)}{\sum_{x \in U_i(1)} f(x)^2} \\ & \leq & \mu_2(A_{R_{n-1}}) \end{eqnarray*} where we are using the fact that $v$ sums to zero over each set $U_i(1)$. Combining the two inequalities above, we get \begin{eqnarray*} \mu & \leq & \mu_2(A_{\mathcal{P}_n}) + \mu_2(A_{R_{n-1}}) \\ & = & (n-2) + \binom{n-1}{2} - (n-1) \\ & = & \binom{n}{2} - n \end{eqnarray*} Thus we conclude that $\mu_2(A_{R_n}) = \binom n 2 -n$ and this completes the proof of Theorem \ref{thm:rev_eig}. \qed %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% SECTION SEVEN %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Problems and remarks} Consider the stochastic process of pancake flipping: Start with a stack of $n$ pancakes (or $n$ cards). At each step, with probability $1/n$, choose $i$ where $i=1, \ldots, n$ and do a pancake flipping of the first $i$ pancakes. The above process is equivalent to taking a random walk on $\mathcal{P}_n + I$, where $\mathcal{P}_n$ is the pancake graph. The transition probability matrix is then $P=(A(\mathcal{P}_n)+I)/n$. Since the first nontrivial eigenvalue of the normalized Laplacian of $\mathcal{P}_n$ is $1/(n-1)$. Consequently, the first nontrivial eigenvalue of the normalized Laplacian of $\mathcal{P}_n + I$ is $1/n$ and all eigenvalues of the normalized Laplacian of $\mathcal{P}_n + I$ are at most $2-1/n$. It is known that the rate of convergence for random walk is the inverse of $\lambda^{-1}$ where $\lambda= \min \{\lambda_1, 2-\lambda_{n-1}\}$ where $0=\lambda_0, \lambda_1, \ldots, \lambda_{n-1}$ are the nontrivial eigenvalues of the normalized Laplacian of $\mathcal{P}_n + I$. However, in order to get tight bounds for the convergence of the random walk to the stationary distribution under the total variational distance, more work is needed. For a vertex-transitive graph, a general upper bound after $t$ steps of random walk on $\mathcal{P}_n + I$ can be derived by using the Plancherel formula (see \cite{cgn}): \begin{align*} \Delta_{TV}(t) &\leq \frac 1 2 \Big( \sum_{i \not = 0} (1-\lambda_i)^{2t}\Big)^{1/2}. \end{align*} Using the result that $|1-\lambda_i| \leq 1-1/n$ for $i \not = 0$, we have \begin{align*} \Delta_{TV}(t) &< \frac 1 2 \Big(1-\frac 1 n\Big)^t n!\\ &\leq e^{-t/n+n \log n}. \end{align*} Hence, the random walk converges to the uniform distribution with $\Delta_{TV}(t) \leq e^{-c}$ after at most $t=n^2 \log n + c n$ steps. If we know more about the distribution of eigenvalues $\lambda_i$, this upper bound should be improved. It seems reasonable to conjecture that $O(n \log n)$ steps suffice. Similarly, we can consider the random substring reversal process, where in each step, with probability $\binom{n+1}{2}^{-1}$ we choose a substring (allowing substrings of length $1$) and reverse it. This is equivalent to taking a random walk on $R_n+ nI$. In this case, we have $\lambda_1 = n/ \binom {n+1} 2= 2 (n+1)^{-1}$ and $\lambda_{n-1} \leq 2 - 2 (n+1)^{-1}$. As in the case of pancake flipping, knowing the spectral gap allows us to obtain a bound on the rate of convergence, but to obtain sharp bounds it would be desirable to know more about the distribution of all eigenvalues. In this paper, we mainly focus on substring reversal and pancake flipping on permutations. There are many interesting variations of these problems. In particular, for applications such as genome rearrangement, the objects of interest are signed permutations. In this case the operation of substring reversal is taking the reverse of the substring and changing the signs of every element in the substring. The corresponding problem for pancake flipping is the {\it burnt} pancake problem where the sign is used to distinguish the two sides of each pancake. This ``burnt'' variant was studied by Gates and Papadimitriou \cite{Gates1979} (with the restriction that the burnt side is originally face-down and must be face-down when sorted), and by Cohen and Blum \cite{CohenBlum1995}. The burnt pancake graph $\bar{\mathcal P}_n$ has $2^n n!$ vertices and degree $n$. A natural question is to determine the spectral gap of the adjacency matrix. In fact, $\mathcal{P}_n + I$ is a projection of $\bar{\mathcal{P}}_n$, which implies that the adjacency spectral gap of $\bar{\mathcal{P}}_n$ is at least one. A harmless guess is that the spectral gap of the adjacency matrix of $\bar{\mathcal P}_n$ is exactly $1$. However, this turns out to be not true. For $\bar{\mathcal P}_4$ the spectral gap is approximately $0.71343$, and for $\bar{\mathcal P}_5$ the spectral gap is approximately $0.75758$. \begin{thebibliography}{1} \bibitem{AMM} H.~Dweighter. \newblock Problem E2569. \newblock {\em Amer. Math. Monthly}, 82:1010, 1975. \bibitem{BafnaPevzner1996} V.~Bafna, P.~Pevzner. \newblock Genome rearrangements and sorting by reversals. \newblock {\em SIAM Journal on Computing}, 25(2):272--289, 1996. \bibitem{Bulteau2015} L.~Bulteau, G.~Furtin, I.~Rusu. \newblock Pancake Flipping is Hard. \newblock {\em Journal of Computer and System Sciences}, 81(8):1556--1574, 2015. \bibitem{Cesi2009} F~ Cesi. \newblock Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap. \newblock {\em The Electronic Journal of Combinatorics}, 16(1), 2009. \bibitem{Chitturi2009} B.~Chitturi, W.~Fahle, Z.~Meng, L.~Morales, C.O.~Shields, I.H.~Sudborough, W.~Voit. \newblock An upper bound for sorting by prefix reversals. \newblock {\em Theoretical Computer Science}, 410(36):3372, 2009. \bibitem{coverings} F.~Chung, S.-T.~Yau. \newblock Coverings, heat kernels and spanning trees. \newblock {\em Journal of Combinatorics}, 6:163--184, 1998. \bibitem{cgn} F.~Chung, \emph{Spectral Graph Theory}, AMS Publications, Providence, 1997. \bibitem{CohenBlum1995} D.~Cohen, M.~Blum. \newblock On the problem of sorting burnt pancakes. \newblock {\em Discrete Applied Mathematics}, 61(2):105--120, 1995. \bibitem{FlattoEtAl1985} L.~Flatto, A.M.~Odlyzko, D.B.~Wales. \newblock Random shuffles and group representations. \newblock {\em The Annals of Probability}, 13: 154--178, 1985. \bibitem{Friedman2000} J.~Friedman. \newblock On Cayley graphs on the symmetric group generated by tranpositions. \newblock {\em Combinatorica}, 20(4):505--519, 2000. \bibitem{Gates1979} W.~Gates, C.~Papadimitriou. \newblock Bounds For Sorting By Prefix Reversal. \newblock {\em Discrete Mathematics}, {27}:47--57, 1979. \bibitem{agt} C.~Godsil, G.~Royle. \emph{Algebraic Graph Theory}, Springer, New York, 2001. \bibitem{GrossTucker} J.~Gross, T.~Tucker, \emph{Topological graph theory}, Courier Corporation (1987). \bibitem{GunnellsEtAl2007} P.E.~Gunnells, R.A.~Scott, B.L.~Walden. \newblock On certain integral Schreier graphs of the symmetric group. \newblock {\em The Electronic Journal of Combinatorics}, {14}(1) (2007). \bibitem{Hannenhalli1996} S.~Hannenhalli. \newblock Polynomial-time algorithm for computing translocation distance between genomes. \newblock {\em Discrete Applied Mathematics}, {71}(1-3):137--151, 1996. \bibitem{HeydariSudborough} M.H.~Heydari, I.H.~Sudborough. \newblock On the diameter of the pancake network. \newblock {\em J. Algorithms}, {25}(1):67--94, 1997. \bibitem{Kassabov2005} M.~Kassabov. \newblock Symmetric groups and expanders. \newblock {\em Electronic Research Announcements of the American Mathematical Society}, {11}(6), 2005. \bibitem{ks} J.~Kececioglu, D.~Sankof. \newblock Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement.\newblock {\em Algorithmica} {13}:180--210, 1995. \bibitem{LiMeng2008} R.~Li, J.~Meng. \newblock Reversals Cayley graphs of symmetric groups. \newblock {\em Information Processing Letters}, {109}(2) (2008). \bibitem{Lubotzky} A.~Lubotzky. \newblock Cayley graphs: eigenvalues, expanders and random walks. \newblock {\em London Mathematical Society Lecture Note Series}, 155--190, 1995. \end{thebibliography} \end{document}