\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.4}{23(3)}{2016}

% we recommend these ams packages
\usepackage{amsmath,amsthm,amssymb,mathrsfs}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\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{proposition}[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}

%eigenlb_ejc.tex
%\documentclass[11pt]{article}
%\usepackage{graphicx}
%\usepackage{amsmath, mathrsfs}
%\usepackage{amssymb}

\newcommand{\vect}[1]{\boldsymbol{#1}}
%\newtheorem{fact}{Fact}

\newtheorem{cor}[theorem]{Corollary}


\newcommand{\diam}{{\rm diam}}
\newcommand{\ppr}{{\rm pr}}
\newcommand{\vol}{{\rm vol}}
\newcommand{\LL}{{\mathcal L}}
\newcommand{\FF}{{\mathcal F}}
\newcommand{\TT}{{\mathcal T}}
\newcommand{\XX}{{\mathcal X}}
\newcommand{\CC}{{\mathcal C}}


\newcommand{\ignore}[1]{}


\title{\bf  A generalized  Alon-Boppana bound \\and weak Ramanujan  graphs}
\author{
 Fan Chung\thanks{Research  supported in part by AFSOR FA9550-09-1-0090.}\\
 \small Department of Mathematics\\[-0.8ex]
\small University of California, San Diego\\[-0.8ex] 
\small La Jolla, CA, U.S.A.\\[-0.8ex]
\small\tt fan@ucsd.edu
 }

\date{\dateline{Feb 10, 2016}{Jun 24, 2016}{Jul 8, 2016}\\
\small Mathematics Subject Classifications: 05C50}

\allowdisplaybreaks
\begin{document}
\maketitle

%\thispagestyle{first} \setcounter{page}{1}



\begin{abstract}
%\vskip 3mm
%\footnotesize
A basic eigenvalue bound due to Alon and Boppana holds only for regular graphs.
In this paper we give a generalized Alon-Boppana bound for eigenvalues of graphs that are not required to be regular. We show that a  graph $G$ with  diameter $k$ and vertex set $V$, the smallest nontrivial eigenvalue $\lambda_1$ of the normalized Laplacian $\mathcal L$ satisfies
 \begin{align*}
 \lambda_1 \leq 1-\sigma  \big(1- \frac c {k} \big)
 \end{align*}
 for some constant $c$
where  $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2 $ and $d_v$ denotes the degree of the vertex $v$. 

We  consider weak Ramanujan graphs defined as  graphs satisfying $ \lambda_1 \geq 1-\sigma$.
We examine  the vertex expansion and edge expansion of weak Ramanujan graphs and then use the expansion properties among other methods to derive  the above Alon-Boppana bound.

\end{abstract}

%\vskip 12mm

\section{Introduction} \label{intro}
%%\setzero
%\vskip-5mm \hspace{5mm }

The well-known Alon-Boppana bound \cite{ab} states that  for any $d$-regular graph with diameter $k$, the second largest eigenvalue $\rho$ of the adjacency matrix satisfies
 \begin{align}\label{e1}
 \rho \geq 2 \sqrt{d-1} \Big(1- \frac 2 {k} \Big)-  \frac 2 {k}. 
 \end{align}

A natural question is to extend Alon-Boppana bounds for graphs  that are irregular. 
 Hoory \cite{hoo} showed that for an irregular graph, the second largest eigenvalue $\rho$ of
the adjacency matrix satisfies
\begin{align*}
\rho \geq 2 \sqrt{d-1} \Big(1-\frac {c \log r} {r} \Big)
\end{align*}
if the average degree of the graph after deleting   a ball of radius $r$ is at least $d$ where $r, d >2$.

For irregular graphs, it is often advantageous to consider eigenvalues
of the normalized Laplacian for deriving various graph properties. For a graph $G$, the normalized Laplacian $\mathcal L$, defined by
\[ {\mathcal L} = I - D^{-1/2}AD^{-1/2} \]
where $D$ is the diagonal degree matrix and $A$ denotes the adjacency matrix of $G$.
One of the main tools for dealing with general graphs is the Cheeger inequality which  relates the least nontrivial eigenvalue $\lambda_1$ to the Cheeger constant $h_G$:
\begin{align}
\label{chee} 2h_G \geq \lambda_1 \geq \frac{h_G^2} 2 \end{align}
where $h_G = \min_S |\partial(S)|/\vol(S)$ for $S$ ranging over all vertex subsets with 
volume $\vol(S)=\sum_{u \in S} d_u$ no more than half of $\sum_{u \in V} d_u$ and  $\partial(S)$ denotes the set of edges leaving $S$.
 For $k$-regular graphs, we have $\lambda_1= 1-\rho/k$ where $\rho $ denotes the second largest eigenvalue of the adjacency matrix.  In general, $$\frac{\rho}{\max_v d_v} \leq  1- \lambda_1 \leq \frac{\rho}{ \min_v d_v}$$
which can be used to derive a version  of the Cheeger inequality involving $\rho$ which is less effective  than (\ref{chee}) for irregular graphs.

 
 
In this paper, we will show that for a connected graph $G$ with diameter $k$, $\lambda_1$ is upper bounded by
\begin{align}\label{e2}
 \lambda_1 \leq 1-\sigma (1 - \frac c {k} )
 \end{align}
 for a constant $c$ where  $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2 $.
The above inequality  will be proved in Section \ref{sec3}. 
 
 The above bound of Alon-Boppana type  improves a result of Young \cite{young} who
 derived a similar eigenvalue bound using a different method. 
In \cite{young}  the notion of $ (r,d,\delta)$-robust graphs was considered and it was shown that  for a $(r, d, \delta)$-robust
 graph, the least nontrivial eigenvalue $\lambda_1$ satisfies
 \begin{align}\label{e3}
 \lambda_1 \leq 1-\frac{ 2 d \sqrt{d-1}}{\delta}  \Big(1- \frac c {r} \Big).
 \end{align}
Here $ (r, d, \delta)$-robustness means
for every vertex $v$  and the ball  $B_r(v)$ consisting of all vertices with distance at most $r$,
 the induced subgraph on the complement of $ B_r(v)$ has 
 average degree at least $d$ and  $\sum_{v \not \in B_r(v)}d_v^2/|V \setminus B_r(v)| \leq \delta$. 
We remark that our result in (\ref{e2}) does not require the  condition of robustness.

We define  {\it weak Ramanujan} graphs to be graphs with eigenvalue $\lambda_1$ satisfying
\begin{align}\label{e22}
 \lambda_1 \geq 1-\sigma \geq \frac 1 2 
 \end{align}
 where  $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2 $.
 
 To prove the Alon-Boppana bound in (\ref{e2}), it suffices to consider only weak Ramanujan graphs. Weak Ramanujan graphs satisfy various expansion properties.
 We will describe several vertex-expansion and edge-expansion properties involving $\lambda_1$ in Section \ref{secex}, which will be needed later for proving a diameter bound for weak Ramanujan graphs in Section \ref{wram}. The diameter bound and related properties of weak Ramanujan graphs are useful in the proof of the Alon-Boppana bound for general graphs.
 
 
 
We will also show that the largest eigenvalue $\lambda_{n-1}$ of the normalized Laplacian satisfies
\begin{align}
\lambda_{n-1} \geq 1+\sigma (1 - \frac {c} {k} ).
 \end{align}
The proof will be given in Section \ref{sec4}.

\ignore{
We define  {\it strong Ramanujan} graphs to be graphs which satisfy 
\begin{align}\label{e22}
\max_{i \not = 0} |1- \lambda_{i} |\leq \Big[\frac{ 2 \sqrt{d_v-1}}{d_v}\Big]_{v \in V}^{(2)}.
 \end{align}
 
Of course the   strong Ramanujan graphs satisfy further properties  including the discrepancy inequality which we will mention in Section \ref{secex}.
}
\section{Preliminaries}

\vskip-5mm \hspace{5mm }



For a graph $G=(V,E)$, we consider the normalized Laplacian
\[ {\mathcal L}=I-D^{-1/2}A D^{-1/2} \]
where $A$ denotes the adjacency matrix and $D$ denotes the diagonal degree matrix with
$D(v,v)=d_v$, the degree of $v$. We assume that there is no isolated vertex throughout this paper.  For a vertex $v$ and a positive integer $l$, let $B_l(v)$ denote the ball consisting of all vertices within distance $l$ from $v$. For an edge $\{x,y\} \in E$ we say $x$ is adjacent to $y$
and write $x \sim y$.

Let $\lambda_0 \leq \lambda_1 \leq \ldots \leq \lambda_{n-1} $ denote eigenvalues of $\mathcal L$, where $n$ denotes the number of vertices in $G$. It can be checked (see \cite{ch0}) that $\lambda_1>0$ if $G$ is connected. The Alon-Boppana bound obviously holds if $\lambda_1=0$. In the remainder of this paper,
we assume $G$ is connected. 

Let $\varphi_i$ denote the orthonormal eigenvector associated with eigenvalue $\lambda_i$. In particular,
$\varphi_0 = D^{1/2} {\mathbf 1}/\sqrt{\vol(G)}$  where $\mathbf 1$ is the all $1$'s vector and $\vol(G)=\sum_{v \in V} d_v$.
We can then write
\begin{align*}
\lambda_1 &= \inf_{g \perp \varphi_0} \frac{\langle g, {\mathcal L} g \rangle}{\langle g, g \rangle}\\
&= \inf_{f \perp D {\mathbf 1}} \frac{\sum_{x \sim y} \big(f(x)-f(y)\big)^2}{\sum_z f^2(z)d_z}\\
&= \inf_{f \perp D {\mathbf 1}} R(f)
\end{align*}
where $f$ ranges over all functions satisfying $\sum_u f(u) d_u=0$ and the sum $\sum_{x \sim y}$ ranges over all
unordered pairs $\{x, y \}$ where  $x$ is adjacent to $y$. Here $R(f)$ denote the {\it Rayleigh quotient} of $f$, which can be written as follows:
\begin{align*} R(f)&= \frac{\int |\nabla f|}{\int \|f\|^2}\\
\mbox{where    } \int \|f\|^2&= \sum_x f^2(x)d_x\\
\mbox{and        } \int |\nabla f|&=\sum_{x \sim y} \big(f(x)-f(y)\big)^2.
\end{align*}

For eigenfunction $\varphi_i$, the  function $f_i= D^{-1/2} \varphi_i $, called  the combinatorial eigenfucntion associated with $\lambda_i$, satisfies
\begin{align}
\label{ff}
\lambda_i f(u) d_u = \sum_{v \sim u} \big(f(u)-f(v)\big) \end{align}
for each vertex $u$. In particular, for $f$ satisfying $\sum_u f(u) d_u=0$, we have
\begin{align}
\label{ff1}
\langle f, Af \rangle \leq  (1-\lambda_1) \langle f, Df \rangle 
\end{align}
and \vspace{-.2in}
\begin{align}
\label{ff2}
|\langle f, Af \rangle| \leq  \max_{i \not =0} (1-\lambda_i) \langle f, Df \rangle.
\end{align}

\ignore{
\subsection{Higher order volume and higher order average}
The $i$-volume of a subset $S$ is defined by
\[ \vol_i(S)= \sum_{v \in S} d_v^i.\]
In particular, $\vol_0(S)=|S|$ denotes the cardinality of $S$.
For $i=1$,  we have $\vol_1(S)=\sum_{v \in S} d_v$ and   we call $\vol_1(S)=\vol(S)$ the  volume of $S$.
The total $i$-volume of $G$ is denoted by
\[ \vol_i(G)= \sum_{v \in V} d^i_v. \]


For a function $f : V \rightarrow {\mathbb R}$, the $i$-weighted average of $f$ is defined by
\begin{align*}
\big[f(v)\big]^{(i)} = \frac{\sum_{v \in V} f(v)d_v^i}{\sum_{v \in V} d_v^i}.
\end{align*}
}
\section{Vertex and edge expansions }
\label{secex}
 For any subset $S$  of vertices, there are two types of boundaries. The {\it edge boundary} of $S$, denoted by $\partial(S)$ consists of all edges with exactly one endpoint in $S$.
The {\it vertex boundary} of $S$, denoted by $\delta(S)$ consists of all vertices not in $S$ but adjacent to vertices in $S$. Namely,
\begin{align*}
\partial(S)&= \{ \{u,v\} \in E~:~ u \in S~\text{and}~ v \not \in S \}=E(S, \bar{S})\\
\delta(S)&= \{ u \not \in S ~:~  u \sim v \in S ~\text{for some vertex}~v\}
\end{align*}

In this section, we will examine vertex expansion and edge expansion relying only
on $\lambda_1$.  These expansion properties will be needed for deriving diameter bounds for weak Ramanujan graphs which will be used in our proof of the general Alon-Boppana bound later in Section \ref{sec3}.

From the definition of the  Cheeger constant, for all vertex subsets $S$, we have 
\begin{align*}
\frac{|\partial(S)|} {\vol(S)} \geq h_G \geq \frac {\lambda_1} 2
\end{align*}
Later in the proofs, we will be interested in the case that $\vol(S)$ is small and therefore we will use the following version. 
\begin{lemma}
\label{t52}
Let $S$ be a subset of vertices in $G$. Then
\begin{align*}
\frac{|\partial(S)| }{\vol (S)} &\geq  \lambda_1\Big(1- \frac{\vol(S)}{\vol(G)}\Big).
\end{align*} 
\end{lemma}
\begin{proof}
Suppose $f$ is defined by
$$f= \frac{{\mathbf 1}_S}{\vol(S)}-\frac{{\mathbf 1}_{\bar{S}}}{\vol(\bar{S})}$$
where ${\mathbf 1}_S$ denotes the characteristic function defined by ${\mathbf 1}_S(v)=1$ if $v \in S$ and $0$ otherwise.

The Rayleigh quotient $R(f)$ satisfies
\begin{align*}
\lambda_1 \leq R(f)&= \frac{|\partial(S)| }{\vol(S)} \cdot \frac{\vol(G)}{\vol(\bar{S})}.\qedhere
\end{align*}
\end{proof}



 For the expansion of the vertex boundary, the Tanner bound \cite{tanner} for regular graphs can be generalized as follows. 
\begin{lemma}
Let $\bar{\lambda} = \min_{i \not = 0} |1- \lambda_i|.$
Then for any vertex subset $S$ in a graph,
\begin{align}\label{delta}
\frac {\vol(\delta(S))}{\vol(S)} \geq \frac {1- \bar\lambda^2}{\bar\lambda^2 + \frac{\vol(S)}{\vol(\overline{S})}}
\end{align}
\end{lemma}

The proof of the above inequality is by using the following  discrepancy inequality (as seen in \cite{ch0}).

\begin{lemma}
\label{ma53}
 In a  graph $G$, for two subset $X$ and $Y$ of vertices, the number $e(X,Y)=|E(X,Y)|$of edges between
$X$ and $Y$ satisfies
 \begin{align}\label{disc}
 \left| e(X,Y)- \frac{\vol(X)\vol(Y)}{\vol(G)}\right| \leq \bar{\lambda} \frac{\sqrt{\vol(X)\vol(Y)\vol(\overline{X})\vol(\overline{Y})}}{\vol(G)}
 \end{align}
 where $\bar{\lambda} = \min_{i \not = 0} |1- \lambda_i|.$
 \end{lemma}
The proof of Lemma \ref{ma53} follows from (\ref{ff2}) and can be found in \cite{ch0}. The proof of  (\ref{delta}) results from
(\ref{disc}) by setting $X=S$ and $Y= \overline{ S \cup \delta(S)}$.


 
 
 
 
  Here we will give a version of the  vertex-expansion bounds   for general graphs which only rely on $\lambda_1$ and are independent of other eigenvalues.  
 \begin{lemma}
 \label{t53}
In a graph $G$ with vertex set $V$ and  the first nontrivial eigenvalue $\lambda_1$, for    a subset $S$ of $V$ with $\vol(S \cup \delta S) \leq \epsilon \vol(G) \leq  \vol(G)/2$,  the vertex boundary of $S$ satisfies\\
%\vspace{.2in}

\noindent
(i) \vspace{-.4in}
 \begin{align}\label{delta}
 \frac{\vol(\delta(S))}{\vol(S)} &\geq \frac{2\lambda_1}{1-\lambda_1+2\epsilon } 
 \end{align}
 (ii) If $1/2 \leq \lambda_1 \leq 1-2\epsilon$, then
 \vspace{-.1in}
 \begin{align}\label{delta1}
 \frac{\vol(\delta(S))}{\vol(S)} &\geq \frac{1}{(1-\lambda_1+ 2\epsilon)^2 }.
  \end{align}
 \end{lemma}
 \begin{proof}
 The proof of (i) follows  from Lemma \ref{t52} since
 \begin{align*}
 \frac{\vol(\delta(S))}{\vol(S)} &\geq \frac{|\partial (S \cup \delta(S))|+|\partial(S)|}{\vol(S)}\\
 &\geq \frac{\lambda_1(1-\epsilon) \big(\vol(S)+\vol(\delta(S)\big) + \lambda_1(1-\epsilon) \vol(S)}{\vol(S)}
 \end{align*}
 Therefore
  \begin{align*}
 \frac{\vol(\delta(S))}{\vol(S)} &\geq \frac{2\lambda_1(1-\epsilon)}{1-\lambda_1(1-\epsilon)}\geq \frac{2 \lambda_1}{1-\lambda_1 + 2 \epsilon}
 \end{align*}
 To prove (ii),
 we set $f= {\mathbf 1}_S + \gamma {\mathbf 1}_{\delta(S)}$ where $\gamma=1-\lambda_1$. Consider $g=f-c {\mathbf 1}_V$ where $c =\sum_uf(u)d_u \Big/ \vol(G)$. By the Cauchy-Schwarz inequality, we have
 \begin{align*}
 c^2  = \frac 1 {(\vol(G))^2}\Big(\sum_{u \in S \cup \delta(S)} f(u)d_u \Big)^2&\leq  \frac{\vol(S\cup \delta(S))} {(\vol(G))^2}\sum_u f^2(u)d_u\\
 &\leq \frac{\epsilon}{\vol(G)} \sum_u f^2(u)d_u.
 \end{align*}
 
 Using the inequality in (\ref{ff1}), we have
 \begin{align*}
 \langle f, A f \rangle &\leq \langle g, A g \rangle + c^2 \vol(G)\\
 &\leq \gamma \langle g, D g\rangle + c^2 \vol(G)\\
 &= \gamma \langle f, D f \rangle +(1-\gamma) c^2 \vol(G)\\
 &\leq (\gamma+  \epsilon) \langle f, D f \rangle\\
 &= (\gamma+ \epsilon) \big(\vol(S)+ \gamma^2 \vol(\delta(S))\big).
   \end{align*}
  Let $e(S,T)$ denote the number of ordered pairs $(u,v)$ where $u \in S, v \in T$ and
  $\{u,v\} \in E$. Since $\gamma = 1-\lambda \leq 1/2$, we have
   \begin{align*}
 \langle f, Af \rangle &\geq e(S,S)+ 2 \gamma e(S, \delta(S))\\
 &\geq (1-2\gamma) e(S,S)+ 2 \gamma \vol(S)\\
 &\geq 2 \gamma \vol(S)
 \end{align*}
 Together we have
 \begin{align*}
 \frac{\vol(\delta(S))}{\vol(S)}&\geq \frac{\gamma -  \epsilon}
 {\sigma^2 ( \gamma+ \epsilon)}\\
 &\geq \frac {1}{(\gamma + 2 \epsilon)^2}
 \end{align*}
 since $\gamma \geq 2 \epsilon$.
 \end{proof}

 
 \vspace{.1in}
Recall that   weak Ramanujan graphs have eigenvalue $\lambda_1$ satisfying
\begin{align}\label{e22}
 \lambda_1 \geq 1-\sigma 
 \end{align}
 where  $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2 $.
Lemma \ref{t52} implies that for $S$ with $\vol(S \cup \delta(S)) \leq \epsilon \vol(G)$, 
\begin{align*}
\frac{\vol(\delta(S)) }{\vol (S)}&\geq  \frac 1{(\sigma+ 2 \epsilon)^2}.
\end{align*} 

 For $k$-regular Ramanujan graphs with eigenvalue $\lambda_1=1-2 \sqrt{k-1}/k$,
 the above inequality is consistent with the bound
 \begin{align*}
\frac{\vol(\delta(S)) }{\vol (S)}= \frac{|\delta(S)|}{|S|}  &\geq  \frac 1 {(\frac {2 \sqrt{k-1}} k + 2 \epsilon)^2}\end{align*}
which is about $k/4$ when $\vol(S)$ is small. The factor $k/4$ in the above inequality was  improved by Kahale \cite{kahale} to $k/2$.
There are many applications (see \cite{loss}) that require  graphs having expansion factor to be $(1-\epsilon)k$. Such graphs are called {\it lossless} expanders.
In \cite{loss}, lossless graphs were constructed explicitly by using the zig-zag construction but the method for deriving  the expansion bounds does not use   eigenvalues. In this paper, the expansion factor as in Lemma \ref{t53} is enough for our proof later.

\section{Weak Ramanujan graphs}\label{wram}
 We recall that a graph is said to be a weak Ramanujan graph  as in (\ref{e22}) if
 $$\lambda_1 \geq 1-\sigma \geq \frac 1 2$$
where
\begin{align}
\label{sigma} \sigma = 2\frac{\sum_v d_v \sqrt{d_v-1}}{\sum_v d_v^2 }.
\end{align}
To prove the Alon-Boppana bound, it is enough to consider only weak Ramanujan graphs.

\begin{lemma}\label{ma1}
As defined in (\ref{sigma}), $\sigma$ satisfies
\begin{align*}
\frac{2 \sqrt{\bar d -1}}{\breve{d}}\leq \sigma \leq
\frac{2 \sqrt{\bar d -1}}{\bar d} 
\end{align*}
 where $\bar d $ denotes  the average degree in $G$ and $\breve{d}$ denote the second order degree, i.e.,
\begin{align*}
\bar d = \frac{\sum_{v} d_v}{n} ~~\text{and}~~~
\breve{d}= \frac{\sum_v d^2_v}{\sum_v d_v}.
\end{align*}
\end{lemma}
\begin{proof}
The proof is mainly by using the Cauchy-Schwarz inequality. For the upper bound, we note that
\begin{align*}
\sigma = 2\frac{\sum_v  d_v \sqrt{d_v-1}}{\sum_v d_v^2}
&\leq 2 \frac {\sqrt{\sum_v d^2 \sum_v(d_v-1)
}}
{\sum_v d^2_v}\\
&=  2\frac {\sqrt{ \sum_v(d_v-1)
}}
{\sqrt{\sum_v d^2_v}}\\
&\leq 2\frac {\sqrt{ \sum_v(d_v-1)
}}
{{\sum_v d_v}/{\sqrt{n}}}\\
&\leq 2\frac {\sqrt{ \sum_v(d_v-1)
}}
{\bar d {\sqrt{n}}} \leq \frac{2 \sqrt{\bar d -1}}{\bar d}.
\end{align*}
For the upper bound, we will use the fact that   for $a, b > 1 $ and $a+b=c$,
$$a \sqrt{a-1} + b \sqrt{b-1} \geq c \sqrt{ \frac{c} 2 -1}$$
and therefore
\begin{align*}
\sum_v d_v \sqrt{d_v-1} &\geq \sum_v d_v  \sqrt{\frac{\sum_v d_v}n -1}.
\end{align*}
Consequently, we have
\begin{align*}
\sigma = 2\frac{\sum_v  d_v \sqrt{d_v-1}}{\sum_v d_v^2}
&\geq 2 \frac {\sum_v d_v \sqrt{ \frac{\sum_v d_v} n -1}}
{\frac{\sum_v d^2_v}{\sum_v d_v} \sum_v d_v}
\geq 2 \frac{\sqrt{\bar d -1}}{\breve{d}}
\end{align*}
as desired.
\end{proof}



We remark that 
for graphs with average degree at least $20$, we have  $\sigma < 1/2 < \lambda_1$.

\begin{theorem}
\label{t41}
Suppose a weak Ramanujan graph $G$ has diameter  $k$. Then for any $\epsilon > 0$, we have
$$k \leq (1+\epsilon) \frac{ 2\log \vol(G)}{\log \sigma^{-1}}$$
provided that the volume of $G$ is large, i.e., $\vol(G) \geq c \sigma^{\log(\sigma)}/\epsilon$ for some small constant $c$.
\end{theorem}
\begin{proof}
 We set  $$t= \Big\lceil(1+\epsilon)  \frac{ \log (\vol(G))}{\log \sigma^{-1}} \Big \rceil.$$
 It suffices to show that for every vertex $v$,
the ball $B_t(v)$ has volume more than $ \vol(G)/2$.

Suppose $\vol(B_t(v)) \leq \vol(G)/2.$
 Let
\begin{align*}
s_j &= \frac {\vol(B_j(u))}{\vol(G)}
.
\end{align*}
By part (i) of Lemma \ref{t53}, we have $\vol(\delta(B_u(j))) \geq  0.5 \vol(B_u(j)) $ for $j \leq t-1$ and therefore
$
s_{j+1} \geq 1.5 s_j$
. Thus, if $j \leq t - c_1 \log (\sigma^{-1})$, then  $s_j \leq \sigma^4$ where $c_1$ is some small constant satisfying $ c_1 \leq 4(\log 1.5)^{-1}$. 

Now we apply part (ii) of Lemma \ref{t53} and  we have, for $j \leq t - c_1 \log (\sigma^{-1})$,
\begin{align*}
\frac{s_{j+1}}{s_j}&=\frac{\vol(B_{j+1}(u))}{\vol(B_j(u))}  
\geq  \frac{\vol(\delta(B_j(u)))}{\vol(B_j(u))}
\geq  \frac 1 {(\sigma+2 s_j)^2}
\geq \frac 1 {(\sigma+ 2 \sigma^4)}.
\end{align*}
This implies, for $l \leq   t - c_1 \log (\sigma^{-1})$,
\begin{align*}
\frac{s_l}{s_0} \geq \prod_{0< j < l} \frac 1 {(\sigma+2 s_j)^2} &\geq \prod_{0< j < l} \frac 1 {(\sigma+2 \sigma^{4})^2}\\
&\geq \frac 1 {\sigma^{2l} (1+ 2 \sigma^4)^{2l}}.
\end{align*}
Since $s_0 \geq  1/{\vol(G)}$ and $s_l \leq s_t \leq 1/2$, we have
\begin{align*}
{\vol(G)} &\geq \frac 1 {\sigma^{2l} (1+ 2 \sigma^4)^{2l}}.
\end{align*}
Hence
\begin{align*}
l \leq \frac {\log( \vol(G))}{\log (\sigma^{-1}) + 2 \sigma^4}.
\end{align*}
However,
\begin{align*}
(1+\epsilon)  \frac{ \log (\vol(G))}{\log( \sigma^{-1})} \leq t \leq c_1 \log (\sigma^{-1})+\frac {\log (\vol(G))}{\log (\sigma^{-1}) + 2 \sigma^4}
\end{align*}
which is a contracdiction for $G$ with $\vol(G) $ large, say, $\vol(G) \geq \sigma^{2c_1 \log \sigma}/\epsilon$. Thus we conclude that $s_t \geq 1/2$ and  Theorem \ref{t41}
is proved.
\end{proof}


\ignore{
We can also establish a lower bound for weak Ramanujan graphs.
\begin{theorem}\label{t42}
For  a weak Ramanujan graph  on $n$ vertices with diameter $k$, we have
\begin{align*}
k \geq c \log n.
\end{align*}
\end{theorem}
\begin{proof}
We consider the matrix
\[ M = \frac{I+D^{-1/2}AD^{-1/2}} 2= I-\frac{\cal L} 2.\]
$M$ has eigenvalues $1-\lambda_i/2$ where $\lambda_i$ are eigenvalues of the normalized Laplacian $\mathcal L$. Since we assume the graph $G$ is weak Ramanujan,
we have
\begin{align*}
1- \frac {\lambda_1} 2 &\leq \frac{1+ \sigma} 2 \leq \frac 3 4
~~~\text{and} ~~~  0 \leq 1- \frac{\lambda_i} 2 \leq  3/4
\end{align*}
for $i \geq 1$. 
Suppose $\phi_i$'s are eigenvector of $\mathcal L$ associated with eigenvalues $\lambda_i$.
For  two vertices $u$ and $v$ at distance $k$ in $G$, we consider
\begin{align*}
{\mathbf 1}_u D^{1/2}&= \sum_{i=0}^{n-1} \alpha_i \phi_i ~~~\text{and}~~~
{\mathbf 1}_v D^{1/2}= \sum_{i=0}^{n-1} \beta_i \phi_i
\end{align*}
Since $G$ has diameter $k$, we have
\begin{align*}
0&=  {\mathbf 1}_u D^{1/2} M^{k-1} D^{1/2} {\mathbf 1}_v\\
&= \alpha_0 \beta_0 + \sum_{i=1}^{n-1} (1-\frac{\lambda_i} 2)^{k-1} \alpha_i \beta_i\\
&\geq \frac{d_u d_v}{\vol(G)} - \max_{i > 1} \big|1-\frac{\lambda_i} 2 \big|^{k-1} \sum_i |\alpha_i \beta_i|\\
&\geq \frac{d_u d_v}{\vol(G)} - \Big(\frac 3 4 \Big)^{k-1} \sqrt{d_u d_v}.
\end{align*}
This implies that
\begin{align*}
\Big(\frac 3 4 \Big)^{k-1} \geq \frac 1 {\vol(G)} \geq \frac 1 {n^2}.
\end{align*}
Therefore, we conclude 
\begin{align*}
k &\geq  c \log n
\end{align*}
for some constant $c$.
\end{proof}

}
\begin{theorem}
\label{t43}
For a weak Ramanujan graph with diameter $k$,
 for any vertex $v$ and any $l \leq k/4$, the ball $B_u(l)$ has volume  at most $\epsilon \vol(G)$
if  $k \geq  c \log \epsilon^{-1}$, for some constants $c$.
\end{theorem}
\begin{proof}
We will prove by contradiction.
Suppose that for $j_0= \lceil k/4 \rceil$, there is a vertex $u$ with  $\vol(B_v(j_0)) > \epsilon \vol(G)$.  
 Let $r$ denote the largest integer  such that 
\begin{align*}
s_r &= \frac {\vol(B_u(r))}{\vol(G)} > \frac 1 2
.
\end{align*}

By the assumption, we have  $r > k/4$ and $s_{j_0} > \epsilon$. There are  two possibilities:

\vspace{.1in}
\noindent
{\it Case 1:}  $ r \geq k/2$.\\
By part (i) of Lemma \ref{t53}, we have $\vol(\delta(B_u(j))) \geq  0.5 \vol(B_u(j)) $ for $j \leq k/2$ and  therefore
$
s_{j+1} \geq 1.5 s_j$
. Thus, for  $j \leq k/2 - c_1 \log \epsilon^{-1}$,  we have $s_j \leq \epsilon$ where $c_1 = 1/\log 1.5$. Since $k/4 \leq k/2 -  c_1 \log \epsilon^{-1}$, we have a contradiction.

\vspace{.1in}
\noindent
{\it Case 2:}  $ r < k/2$.\\
We define
\begin{align*}
\bar{s}_j &= \frac { \vol(V \setminus B_u(j))}{\vol(G)} 
.
\end{align*}
Thus $\bar{s}_j < 1/2$ for all $j \geq k/ 2$. 
We consider two subcases.

\vspace{.1in}
\noindent
{\it Subcase 2a:} Suppose $\bar{s}_j \geq \epsilon$ for $j \geq k/2$.

Using Lemma \ref{t53}, for $j$ where $r \leq j \leq k/2$, we have $
\bar{s}_{j} \geq 1.5 \bar{s}_{j+1}$. Thus, for some $j_1 \geq k/2-c_1 \log \epsilon^{-1}$, we have $\bar{s}_j \geq 1/2$ or equivalently, $s_j \leq 1/2$. By using  Lemma \ref{t53} again, for $j \leq j_1$, we have $s_{j+1} \geq 1.5 s_j$ and therefore
for any $j \leq j_1 - c_1\log \epsilon^{-1}$ we have $ s_j \leq \epsilon$. Since
$j_1 - c_1 \log \epsilon^{-1} \geq k/2 - 2 c_1 \log \epsilon^{-1} \geq k/4$, we again have a contradiction to the assumption $s_{j_0}\geq \epsilon$.


\vspace{.1in}
\noindent
{\it Subcase 2b:} Suppose $\bar{s}_j < \epsilon$ for $j \geq k/2$

We apply part (ii) of Lemma \ref{t53} and  we have, for $j \geq k/2$,
\begin{align*}
\frac{\bar{s}_{j}}{\bar{s}_{j+1}}&  
\geq  \frac 1 {(\sigma+2 \epsilon)^2}.
\end{align*}
This implies,  for $j_2=\lceil k/2 \rceil$, 
\begin{align*}
\frac{\bar{s}_{j_2}}{\bar{s}_k} &\geq \prod_{k/2< j \leq k} \frac 1 {(\sigma+2 s_j)^2} 
\geq  \frac 1 {(\sigma+2 \epsilon)^k}.
\end{align*}


Since $\bar{s}_k \geq  1/{\vol(G)}$, we have
\begin{align*}
\bar{s}_{j_1} & \geq  \frac 1 {\vol(G)(\sigma+2 \epsilon)^k}.
\end{align*}
Since the assumption of this subcase is $\bar{s}_{j_1} < \epsilon $, we have
\begin{align*}
k \geq \frac{\log n + \log \epsilon^{-1}}{\log \sigma^{-1}}.
\end{align*}
We now use Lemma \ref{t53} \ and we have, for $j= k/2-j' \geq r$
\begin{align*}
\bar{s}_j & \geq  \frac 1 {\vol(G)(\sigma+2 \epsilon)^{k+2j'}}.
\end{align*}
Therefore, for some $j \leq k/2-\log \epsilon^{-1}/\log \sigma^{-1}$, we have
$\bar{s}_j > 1/2$
which implies $r \geq k/2 -\log \epsilon^{-1}/\log \sigma^{-1}$.

Now we use the same argument as in Case 1 except shifting $r$ by $\log \epsilon^{-1}/\log \sigma^{-1}$. For some $j \leq r - c_1\log \epsilon^{-1} \leq k/2 -\log \epsilon^{-1}/\log \sigma^{-1}- c_1\log \epsilon^{-1} $, we have
$s_j < \epsilon$. Since  $\log \epsilon^{-1}/\log \sigma^{-1}+ c_1\log \epsilon^{-1} < k/4$, this leads to a contradiction and Theorem \ref{t43} is proved.\end{proof} 

\section{Non-backtracking random walks}
Before we proceed to the proof of the Alon-Boppana bound, we will need some basic facts on
non-backtracking random walks. 

A non-backtracking  walk  is a sequence of vertices
${\mathbf p}=(v_0, v_1, \ldots, v_t)$ for some $t$ such that $v_{i-1} \sim v_i$ and  $v_{i+1} \not = v_{i-1}$ for $i=1, \ldots, t-2$. 
The non-backtracking random walk can be described as follows: For $i \geq 1$, at the $i$th step on $v_i$,  choose with
equal probability a neighbor  $u$ of $v_i$ where   $u \not =v_{i-1}$,  move to $u$ and set $v_{i+1}=u$. 
To simplify notation, we call a non-backtracking walk an NB-walk. The modified transition probability matrix
 $\tilde P_k$, for $k = 0,1, \ldots, t-1$, is defined by
\begin{align}\label{nbwalk}
\tilde P_k(u,v)= \begin{cases} P^k(u,v) &\mbox{if } k=0\\
\sum\limits_{{\mathbf p}\in {\mathscr{P}}^{(k)}_{u,v}} w({\mathbf p}) &\mbox{if } k \geq 1
\end{cases}
\end{align}
where the weight $w({\mathbf p})$ for an NB-walk $\mathbf p = (v_0, v_1, \ldots, v_t)$ with $t \geq 1$ is defined to be
\begin{align}
\label{wp} w({\mathbf p}) = \frac 1 {d_{v_0} \prod_{i=1}^{t-1} (d_{v_i}-1)} 
\end{align}
and $\mathscr{P}^{(k)}_{u,v}$ denotes the set of non-backtracking walks from $u$ to $v$.
For a walk ${\mathbf p}=(v_0)$ of length $0$, we define $w({\mathbf p})=1$.

Although a non-backtracking random walk is not a Markov chain, it is closely related to an associated Markov chain
 as we will describe below (also see \cite{hoo}).

For each edge $\{u,v\}$ in $E$, we consider two directed edges $(u,v)$ and $(v,u)$.  Let $\hat E$ denote the 
set consisting of all such directed edges, i.e. $\hat E = \{ (u,v)~: ~ \{u,v\} \in E\}$. We consider a random walk
on $\hat E$ with transition probability matrix $\vect{P}$ defined as follows:
\begin{align*}
\vect{P}((u,v), (u', v'))  = \begin{cases} \frac 1 {d_v-1} & \mbox{if } v = u' \mbox{and } u \not = v'\\
0 &\mbox{otherwise.}
\end{cases}
\end{align*}
Let ${\mathbf 1}_E $ denote the all $1$'s function defined on the edge set $E$ as a row vector.
From the above definition, we have 
 \begin{align}
\label{1e}
 {\mathbf 1}_E \vect{P} = {\mathbf 1}_E.
 \end{align}

In addition, we define the vertex-edge incidence matrix $B$ and $B^*$ for $a \in V$ and $(b,c) \in \hat E$ by
\begin{align*}
B(a, (b,c)) = \begin{cases} 1 &\mbox{if } a=b, \\
0& \mbox{otherwise}
\end{cases}
\end{align*}
\begin{align*}
B^*((b,c),a)) = \begin{cases} 1 &\mbox{if } c=a, \\
0& \mbox{otherwise.}
\end{cases}
\end{align*}


Let ${\mathbf 1}_V$ denote all $1$'s vector defined on the vertex set $V$. Then 
 \begin{align}
 {\mathbf 1}_VB&={\mathbf 1}_E. \label{1vb}
 \end{align}


Although ${\tilde P}_k$ is not a Markov chain,  it is related to the Markov chain determined by $\vect{P}$ on $\hat E$  as follows:

\vspace{.1in}
\noindent
{\it Fact 1:} 
For $l \geq 1$.
\begin{align}
\tilde P_l &= D^{-1} B \vect{P}^{l} B^* \label{pk}
\end{align}
and for the case of $l=0$,  we have  $\tilde{P}_0= I$.

By combining (\ref{1vb}) and (\ref{pk}), we have

%\vspace{.1in}
\noindent
{\it Fact 2:} 
 \begin{align}
 {\mathbf 1}_V D  {\tilde P}_l &= {\mathbf 1}_EB^*={\mathbf 1}_VD.\label{1v}
 \end{align}
Note that ${\mathbf 1}_V D$ is just the degree vector for the graph $G$. Therefore (\ref{1v}) states that the degree vector is an eigenvector of $\tilde P_l$.
Using Fact 1 and 2, we have the following:

\begin{lemma}$\mbox{~~}$\\
(i)~~~For a fixed vertex $x$ and any integer $j\geq 0$, we have
 \begin{align}\label{pk1}
 \sum_{u} d_u \sum_{{\mathbf p} \in \mathscr{P}^{(j)}_{u,x}} w({\mathbf p}) =d_x
 \end{align}
(ii)~~ For a fixed vertex $u$, we have
\begin{align}\label{pk11}
  \sum_{x} \sum_{{\mathbf p} \in \mathscr{P}^{(j)}_{u,x}} w({\mathbf p}) ={\mathbf 1}_u(I + \tilde{P}_1 + \ldots +  \tilde{P}_l) {\mathbf 1}^*=l+1
 \end{align}
 where ${\mathbf 1}_u$ denotes the characteristic function which assumes value $1$ at $u$ and $0$ else where.
 \end{lemma}
 \begin{proof}
The proof of (\ref{pk1}) and (\ref{pk11})  follows from the fact that 
\[{\mathbf 1}_VD\tilde P_j(x)= {\mathbf 1}_V D (D^{-1}B{\mathbf P}^jB^*)={\mathbf 1}_E{\mathbf P}^jB^*=
{\mathbf 1}_E B^*={\mathbf 1}_VD(x)\]
  and ${\mathbf 1}_u \tilde P_j(x) = w({\mathbf p}) $ for ${\mathbf p}
\in \mathscr{P}^{(j)}_{u,x}$.
\end{proof}


\section{An Alon-Boppana bound for  $\lambda_1$}\label{sec3}


\begin{theorem}
\label{t1}
In a  graph $G=(V,E)$ with  diameter $k$,  the first nontrivial eigenvalue $\lambda_1$ satisfies 
\begin{align*}
\lambda_1 \leq 1-\sigma \Big(1- \frac c {k}\Big)
\end{align*} 
where $\sigma$ is as defined in (\ref{sigma}), provided  $k \geq c' \log \sigma^{-1}$ and $\vol(G) \geq c'' \sigma^{\log \sigma}$ for some absolute constants $c$'s. 
\end{theorem}
\begin{proof}
If $G$ is not a weak Ramanujan graph, we have $\lambda_1 \leq 1-\sigma$ and we are done. We may assume that $G$ is weak Ramanujan.

From the definition of $\lambda_1$, we have
\begin{align}
\lambda_1 &\leq \frac{\sum_{x \sim y} (f(x)-f(y))^2}{\sum_x f^2(x) d_x } = R(f)
\label{Rf}
\end{align}
where $f $ satisfies $\sum_x f(x) d_x=0$.

We will construct an appropriate $f$ satisfying $R(f) \leq 1-\sigma (1-  c/k)$ and therefore serve as an upper bound for $\lambda_1$. 
We set
$$t= \Big \lfloor \frac{ \log (\vol(G))}{\log \sigma^{-1}} \Big \rfloor$$
and choose $\epsilon$ satisfying
$$\epsilon \leq \frac{\sigma} t \leq \frac {c \sigma }{k}$$
 by using Theorem \ref{t41} where $\sigma$ is as defined in (\ref{sigma}).




We consider a family of functions defined as follows.
For a specified vertex $u$ and an integer $l = \lfloor k/4 \rfloor$, we consider a function $g_u: V \rightarrow {\mathbb R}^+$, defined by
\begin{align*}
g_u(x)&= \Big( {\mathbf 1}_u ( I + \tilde P_1 + \ldots + \tilde P_l)(x) \Big)^{1/2}\\
&= \Big( \sum_{j=0}^l \sum_{{\mathbf p} \in \mathscr{P}^{(j)}_{u,x} } w({\mathbf p}) \Big)^{1/2}
\end{align*} 
where   $\tilde P_j$ is as defined in (\ref{pk}) and ${\mathbf 1}_u$ is treated as a row vector.
In other words, $g_u$ denotes the square root of the sum of non-backtracking random walks starting from $u$ taking $i$ steps for $i$ ranging from $0$ to $l$.

\vspace{.1in}
\noindent
{\it Claim A:} 
\begin{align*}
\sum_u d_u \sum_x g_u^2(x)d_x &=\sum_{j=0}^l \sum_x\sum\limits_{{\mathbf p}\in \mathscr{P}^{(l)}_{u,x}} d_u w({\mathbf p}) d_x= (l+1) \sum_x d_x^2
\end{align*}
where  the weight $w({\mathbf p})$ of a walk $\mathbf p$ is as defined in (\ref{wp}).\\
\vspace{.1in}
\noindent
{\it Proof of Claim A:}
From the definition of $g_u$ and (\ref{nbwalk}), we have
\begin{align*}
\sum_u d_u \sum_x g_u^2(x)d_x&=\sum_{j=0}^l \sum_x\sum\limits_{{\mathbf p}\in \mathscr{P}^{(l)}_{u,x}} d_u w({\mathbf p})\\
&=
\sum_u d_u {\mathbf 1}_u B( I + \tilde P_1 + \ldots + \tilde P_l)(x) \\
&= 
\sum_u d_u  \sum_{i=1}^l  {\mathbf 1}_u D^{-1}B{\mathbf P}^iB^*(x)d_x + \sum_x d_x^2\\
&=  \sum_{i=1}^l \sum_u {\mathbf 1}_u B {\mathbf P}^iB^*(x)d_x+ \sum_x d_x^2\\
&= \sum_{i=1}^l  {\mathbf 1}_E {\mathbf P}^iB^*(x)d_x+ \sum_x d_x^2\\
&= l {\mathbf 1}_E B^*(x)d_x+ \sum_x d_x^2\\
&= (l+1) \sum_x d_x^2.
\end{align*}
Claim A is proved.


\vspace{.1in}
\noindent
{\it Claim B:} 
\begin{align*}
\sum_u d_u \sum_{x \sim y} \big(g_u(x)-g_u(y)\big)^2 &\leq  (l+1-l\sigma) \sum_x d_x^2.
\end{align*}
where $\sum_{x \sim y}$ denotes the sum ranging over unordered pairs $\{x,y\}$ where $x$ is adjacent to $y$.

\vspace{.1in}
\noindent
{\it Proof of Claim B:}

We will use the following fact for $a_i, b_i > 0$.

\begin{align}
\label{ineq1}
\Big(\sqrt{\sum_i a_i } -\sqrt{\sum_i b_i}\Big)^2 \leq \sum_i \Big(\sqrt{a_i}-\sqrt{b_i}\Big)^2
\end{align}
which can be easily checked.

For a fixed vertex $u$,  we apply Claim B:
\begin{align*}
&\sum_{x \sim y} \big(g_u(x) -g_u(y)\big)^2\\
&= \sum_{x \sim y} \left( \sqrt{  \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x} \\
t \leq l} }w({\mathbf p}) }
-\sqrt{ \sum_{\substack{{\mathbf p}' \in \mathscr{P}^{(t)}_{u,y}\\ t \leq l }} w({\mathbf p'}) }\right)^2\\
&\leq \sum_{t \leq l-1}\sum_{r \in V}\sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,r}\\{\mathbf p}'= {\mathbf p} \cup s \in \mathscr{P}^{(t+1)}_{u,s}}}
\left(\sqrt{w({\mathbf p})} -\sqrt{w({\mathbf p}')       } \right)^2 
+ \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} {w({\mathbf p})}(d_x-1)\\
&\leq \sum_{t \leq l-1}\sum_x \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x}}}
\left(\sqrt{w({\mathbf p})} -\sqrt{\frac{w({\mathbf p})}{d_x-1}         } \right)^2 (d_x-1)
+ \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} \sqrt{w({\mathbf p})}(d_x-1)\\
&\leq \sum_{t \leq l-1}\sum_x \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x}}}
w({\mathbf p}) \Big(1+ \frac 1 {d_x-1}-\frac 2 {\sqrt{d_x-1}}\Big)(d_x-1)
+ \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} w({\mathbf p})(d_x-1)\\
&\leq \sum_{t \leq l-1}\sum_x \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x}}}
w({\mathbf p}) \Big(d_x -2\sqrt{d_x-1}\Big)
+ \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} w({\mathbf p})(d_x-1).
\end{align*}

Using Fact 3, we have
\begin{align*}
&\sum_u d_u \sum_{x \sim y} \big(g_u(x) -g_u(y)\big)^2\\
&\leq \sum_{t \leq l-1} \sum_u d_u \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x}}}
w({\mathbf p}) \Big(d_x -2\sqrt{d_x-1}\Big)
+ \sum_u d_u \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} w({\mathbf p})(d_x-1)\\
&= l \sum_x d_x\big(d_x-2\sqrt{d_x-1}\big)+ \sum_x d_x^2\\
&= l (1-\sigma) \sum_x d_x^2 + \sum_x d_x^2\\
&=\big(l+1-l \sigma \big) \sum_x d_x^2
\end{align*}
This proves Claim B.

\vspace{.1in}
\noindent
{\it Claim C:} 
There is a vertex $u$ satisfying 
\begin{align*}R(g_u) \leq 1-\sigma \big(1-\frac 1{l+1}\big)
\end{align*}



\vspace{.1in}
\noindent
{\it Proof of Claim C:}


Combining Claim A and B, we have
\begin{align}
&\sum_u d_u \sum_{x \sim y} \big(g_u(x) -g_u(y)\big)^2 \nonumber\\
&\leq \big(l+1-l \sigma \big) \sum_x d_x^2\nonumber\\
&\leq \big(l+1-l \sigma \big)\Big(\frac 1 {l+1}\Big) \sum_u d_u\sum_x g^2_u(x) d_x\nonumber\\
&=\Big(1-\frac {l\sigma }{l+1}\Big)\sum_u d_u\sum_x g^2_u(x) d_x \label{AB}
\end{align}
Thus we deduce that there is a vertex $u$ such that
\begin{align}
R(g_u)&= \frac {\sum_{x \sim y} \big(g_u(x) -g_u(y)\big)^2}{\sum_x g^2_u(x) d_x} \nonumber\\
& \leq 1-\frac {l\sigma }{l+1}.\label{e12}
\end{align}

We define
\begin{align*}
\alpha_{v} = \frac{\sum_x g_v(x) d_x}{\sum_{x } d_x}=  \frac{\sum_x g_v(x) d_x}{\vol(G)}
\end{align*}
We consider the function $g'_u$ defined by
\begin{align*}
g'_u(x) ={g_u(x)}- \alpha_u
\end{align*}

Clearly, $g'_u$ satisfies the condition that
\begin{align*}
\sum_x g'_u(x) d_x& = 0
\end{align*}
Hence, we have
\begin{align}
\lambda_1  \leq R(g'_u)
&= \frac{\sum_{x \sim y} \big(g'_u(x)-g'_u(y)\big)^2}{\sum_x {g'}_u^2(x)d_x} \nonumber\\
&=\frac{\sum_{x \sim y} \big(g_u(x)-g_u(y)\big)^2}{\sum_x g_u^2(x)d_x- \alpha_u^2 {\vol(G)}}. \label{e13}
\end{align}

Note that by the Cauchy-Schwarz inequality, we have
\begin{align*}
\Big(\sum_{x \in B_u(l)} g_u(x) d_x \Big)^2 \leq {\vol (B_u(l))} \sum_{x \in B_u(l)} g^2_u(x)d_x.
\end{align*}
and therefore
\[ \alpha_u^2 \leq \frac {\vol (B_u(l))}{\vol(G)^2} \sum_x g^2_u(x)d_x.\]
By substitution into (\ref{e13}) and using (\ref{e12}), we have
\begin{align}
\lambda_1  \leq R(g'_u) 
&\leq \frac{R(g)}{1-\frac{\vol(B_u(l))}{\vol(G)}} 
\leq \frac{1-\sigma\big(1-\frac 1{l+1}\big)}{1-\frac {\vol (B_u(l))}{\vol(G)} }\\
& \leq 1 - \sigma\big(1-\frac 1{l+1}\big) +\frac {\vol (B_u(l))}{\vol(G)}\\
&\leq 1 - \sigma\big(1-\frac c{l+1}\big)
% \nonumber\\
%& \leq 1 - \sigma\big(1-\frac c{l+1}\big) \label{e14}
\end{align}
The last inequality follows from Theorem \ref{t43} and the choice of $\epsilon=\sigma/k$.
 This completes the proof of Theorem \ref{t1}.
\end{proof}


\ignore{
\vspace{.1in}
\noindent
{\it Proof of Claim D:}

We will use the following inequality which basically is the Cauchy-Schwarz inequality.

\begin{align}
\label{inq2}
\sum_{i=1}^n \sqrt{a_i}  \leq   \sqrt{ n \Big(\sum_{i=1}^n a_i\Big)}
\end{align}
for $a_i > 0$.
Thus, from the definition of $g_u$, we have
\begin{align*}
\sum_x g_u(x) d_x &= \sum_x \sqrt{\sum_{i=0}^l \sum_{{\mathbf p} \in P_{u,x}(j)} w({\mathbf p})} d_x\\
&\leq  \sqrt{ \Big( \sum_{x \in B_u(l)} d_x \Big) \Big( \sum_x \sum_{i=0}^l \sum_{{\mathbf p} \in P_{u,x}(j)} w({\mathbf p}) d_x\Big)}\\
&= \sqrt{\vol(B_u(l) \sum_x g_u^2(x)d_x }
\end{align*}




From now on, we let $u$ denote the vertex achieving the minimum of $R(g_u)$. 
Our next goal is to find a vertex $v$ which is at distance at least $2l$ from $u$ with small
$R(g_v)$. In order to achieve this, we consider the following sum.


\vspace{.1in}
\noindent
{\it Claim C:} 
\begin{align*}
\sum_{v \not \in B_u(l)} \sum_x g_u^2(x) d_x \geq (l+1) \sum_{x \not \in B_u(2l)} d_x^2
\end{align*}

\vspace{.1in}
\noindent
{\it Proof of Claim C:}
By the definition of $g$, we have
\begin{align*}
\sum_{v \not \in N_u(l) } d_v \sum_x g_v^2(x) d_x
&= \sum_{v \not \in N_u(l) } d_v \sum_x \sum_{\substack{{\mathbf p} \in P^{(j)}_{v,x}\\
j \leq l}} w({\mathbf p})d_x\\
&\geq \sum_{v \not \in N_u(l) } d_v \sum_{x \not \in N_v(2l)} \sum_{\substack{{\mathbf p} \in P^{(j)}_{v,x}\\
j \leq l}} w({\mathbf p})d_x\\
&= \sum_{v } d_v \sum_{x \not \in N_v(2l)} \sum_{\substack{{\mathbf p} \in P^{(j)}_{v,x}\\
j \leq l}} w({\mathbf p})d_x\\
&=  \sum_{x \not \in N_v(2l)}  \sum_{v } d_v\sum_{\substack{{\mathbf p} \in P^{(j)}_{v,x}\\
j \leq l}} w({\mathbf p})d_x\\
& = (l+1)\sum_{x \not \in N_v(2l)} d_x^2.
\end{align*}
This proves Claim C.


For two  vertices $v$, we define
\begin{align*}
\alpha_{v} = \frac{\sum_x g_v(x) d_x}{\sum_{x \in B_v(l)} d_x}.
\end{align*}
We consider the function $f_{u,v}$ defined by
\begin{align*}
f_{u,v}(x) = \frac{g_u(x)}{\alpha_u}-\frac{g_v(x)}{\alpha_v}.
\end{align*}

Clearly, $f_{u,v}$ satisfies the condition that
\begin{align*}
\sum_x f_{u,v}(x) d_x& = 0
\end{align*}
For a pair of vertices $u,v$ satisfying  ${\rm dist}(u,v) \geq 2l$, we have 
\begin{align}
\lambda &\leq R(f_{u,v})
= \frac{\frac 1 {\alpha_u^2}\sum \limits_{\substack{x \sim y}} (g_u(x)-g_u(y))^2 +\frac 1 {\alpha_v^2}\sum \limits_{\substack{x \sim y}} (g_v(x)-g_v(y))^2}{\frac
1 {\alpha_u^2} \sum\limits_x g_u^2(x) d_x +\frac 1 {\alpha_v^2} \sum\limits_x g_v^2(x) d_x  } \end{align}

Our goal is to find an appropriate pair of $u$ and $v$.
}
\ignore{
Suppose
\begin{align*}
R(g_u) &= 1- \frac{l\sigma}{l+1} - \epsilon\\
&= 1-\sigma'-\epsilon
\end{align*}
which is the minimum value of  $R(g_z)$ ranging over all vertices $z$. Then
There is a vertex $v$  at distance at least $l$ from $u$ with $R(g_v)\leq 1-\sigma'+\epsilon'$
satisfying
\[ \epsilon' {\vol_2(\overline{B_u(2l)})} \leq  {\epsilon} { \vol_2(\vol_2(B_u(2l))}  \]
where $\overline{B_u(2l)}$ denotes the complement of $B_u(2l)$.



\vspace{.1in}
\noindent
{\it Claim D:} 


\vspace{.1in}
\noindent
{\it Proof of Claim D:}\\
We define $\epsilon'$ to be the least value such that every vertex $w$ in $B_u(l)$ satisfies
$R(g_w) \geq 1- \sigma'+ \epsilon'$.

From (\ref{AB}), we have 
\begin{align*}
0&\geq\sum_{v  } d_v \sum_{x \sim y} \big(g_v(x) -g_v(y)\big)^2 -
(1-\sigma') (l+1) \sum_x d_x^2 \\
&\geq   \sum_{v  \in N_u(l) } d_v \sum_{x \sim y} \big(g_v(x) -g_v(y)\big)^2
 +\sum_{v \not \in N_u(l) } d_v \sum_{x \sim y} \big(g_v(x) -g_v(y)\big)^2\\
& ~~~~-(1-\sigma') (l+1) \sum_x d_x^2 \\
 &\geq (1-\sigma' - \epsilon)  \sum_{v  \in N_u(l) } d_v\sum_x g_v^2(x)d_x +
 (1-\sigma' + \epsilon')  \sum_{v  \not \in N_u(l) } d_v\sum_x g_v^2(x)d_x\\
 &~~~~~ -(1-\sigma') (l+1) \sum_x d_x^2   ~~~~~~~~~~~~~~~~~~~~~~~~~~\text{from definitions of $\epsilon$ and $\epsilon'$}\\
 &\geq -\epsilon \sum_{v  \in N_u(l) } d_v\sum_x g_v^2(x)d_x + \epsilon'\sum_{v  \not \in N_u(l) } d_v\sum_x g_v^2(x)d_x~~~~~~~~~\text{from Claim A}\\
 &\geq -\epsilon \Big(\sum_{v } d_v\sum_x g_v^2(x)d_x -
 \sum_{v  \in N_u(l) } d_v\sum_x g_v^2(x)d_x \big) + \epsilon'\sum_{v  \not \in N_u(l) } d_v\sum_x g_v^2(x)d_x
 \\
  &\geq -\epsilon \sum_{v } d_v\sum_x g_v^2(x)d_x + (\epsilon +\epsilon')\sum_{v  \not \in N_u(l) } d_v\sum_x g_v^2(x)d_x
 \\
&\geq -\epsilon \sum_{v   } d_v\sum_x g_v^2(x)d_x + (\epsilon+\epsilon')(l+1)\sum_{x  \not \in N_u(2l) } d_x^2~~~~~~~~~~~~~~~~\text{from Claim C}\\
&\geq -\epsilon (l+1)\sum_xd^2_x + (\epsilon+\epsilon')(l+1)\sum_{x  \not \in N_u(2l) } d_x^2~~~~~~~~~~~~~~~~~~~~~~~\text{from Claim A}
 \end{align*}
This implies
\begin{align*}
\epsilon'\sum_{x  \not \in N_u(2l) } d_x^2 \leq \epsilon \sum_{x   \in N_u(2l) } d_x^2
\end{align*}
and Claim D is proved.


We are now ready to prove Theorem \ref{t1}. We construct our function $f$ using $g_u$ and $g_v$ as follows:

 \begin{align*}
&\leq \sum_{v } d_v \sum_{x \sim y} \big(g_v(x) -g_v(y)\big)^2\\
&\leq \Big(1-\frac {l\sigma }{l+1}\Big) (l+1) \sum_x d_x^2  ~~~~~~\text{by Claim B}\\
&\leq \big(l+1-l\sigma  \big) \frac{l}{l-1} \sum_{x \not \in N_u(2l)} d_x^2 ~~~\text{by being $k$-strong }\\
&\leq \big(l+1-l\sigma  \big) \frac{l}{l-1} \frac 1 {l+1}\sum_{v \not \in N_u(l) } d_v \sum_x g^2_v(x)d_x
\end{align*}
xxx


For two  vertices $u$ and $v$, we define
\begin{align*}
\alpha_{u,v} = \frac{\sum_x \big(g_u(x)-g_v(x) \big)d_x}{\sum_x d_x}.
\end{align*}
We consider the function $f_{u,v}$ defined by
\begin{align*}
f_{u,v}(x) = g_u(x)-g_v(x)-\alpha_{u,v}.
\end{align*}

Clearly, $f_{u,v}$ satisfies the condition that
\begin{align*}
\sum_x f_{u,v}(x) d_x& = 0
\end{align*}
Therefore from (\ref{Rf}), for any pair of vertices $u,v$ satisfying  ${\rm dist}(u,v) \geq k/2$, we have 
\begin{align*}
\lambda &\leq R(f_{u,v})\\
&\leq \frac{\sum \limits_{\substack{x \sim y}} (g_u(x)-g_u(y))^2 +\sum \limits_{\substack{x \sim y}} (g_v(x)-g_v(y))^2}{\sum\limits_x (g_u(x)-\alpha_{u,v})^2 d_x +\sum\limits_x (g_v(x)-\alpha_{u,v})^2 d_x + \alpha^2_{u,v}
\vol(V\setminus N_u(l) \setminus N_v(l)) } \\
&=\frac{\sum\limits_{x \sim y} (g_u(x)-g_u(y))^2 +\sum\limits_{x \sim y} (g_v(x)-g_v(y))^2}{\sum \limits_x g_u^2(x) d_x +\sum \limits_xg_v^2(x) d_x -(\alpha_u^2-\alpha_v^2) \big(\vol(N_u(l)-\vol(N_v(l)\big)}.
\end{align*}
It remains to choose an appropriate  pair of $u$ and $v$ which we will define.

XXX


\vspace{.1in}
\noindent
{\it Claim C:}
Suppose $l \leq k/4$ and $k$ is the strong diameter of $G$. Then
there exist $\beta_{u,v} \geq 0$ for all pairs of vertices $u,v$ with ${\rm dist}(u,v) \geq  l $, such that, for  each fixed vertex $u$, we have
\begin{align*}
\sum_v \beta_{u,v}= d_u 
\end{align*}
{\it Proof of Claim C:}
The values of $\beta$'s will be determined by finding a maximum  flow in the following network. 

The network $H$ has the node set consisting of  $s$ (the source), $t$ (the sink) and 
two disjoint  copies of $V$, denoted by $V_1$ and $V_2$.
For every $u  \in V_1$, the edge $(s, u)$  has capacity $d_u $.
For $u,v \in V_1 \cup V_2$, there is an edge with infinite capacity from   $u$ to $v$ if the associated vertices $u, v$ are at distance at least $l$ in $H$. 
For each vertex $v \in V_2$, the edge $(v,t)$ has capacity $d_v $.
 \begin{figure}[h]
\begin{center}
\includegraphics[scale=.35]{f3.pdf}
  \caption{The network $H$}
  \label{f2}
    \end{center}
\end{figure}

Let $F$ denote the maximum flow for $H$. We want to show that the value of $F$ is $\vol(G)=\sum_u d_u $.  We will prove this by contradiction. Suppose the maximum flow is smaller than $\vol(G)$. 

From the max-flow-min-cut theorem,  there is a minimum cut $C$ with capacity less than $\vol(G)$. The cut $C$ can not be the set  of all edges $(s,u)$ for all $u \in V_1$. Similarly,  $C$ can not be the set  of all edges $(v,t)$ for all $v \in V_2$.
In addition $C$ can not contain any edge between $V_1$ and $V_2$.
Therefore there are two subsets $S_1 \subset V_1$, $S_2 \subset V_2$ such that  $C=\{ (s, u): u \in S_1\} \cup \{ (v, t): v \in S_2 \}$.  From the definition of the network $H$, the capacity of $C$ is exactly 
$\vol(S_1)+\vol(S_2)$.
By the assumption that  the capacity of $C$ is less than
$\vol(G)$,  $S_1$ is a proper subset of $V_1$,  $S_2$ is a proper subset of $V_2$ and 
$\vol(S_1)+\vol(S_2) < \vol(G)$.

We set $S'_1=V_1 \setminus S_1$ and $S'_2=V_2 \setminus S_2$. Since $C$ is a cut, there is no edge in $H$ between $S'_1$ and $S'_2$. 
From the definition of $H$, any vertex  $u$ in $G$ with its corresponding vertex in $S'_1$ is at distance at most $l$ from  any vertex  $v$ in $G$ with its corresponding vertex in $S'_2$.
This implies that any two vertices with the corresponding vertices in $S'_1$ are within distance no more than $2l \leq k/2$. Therefore 
$$\vol(S'_1) \leq \vol(B_u(2l)) \leq \vol(G)/2$$ for any fixed vertex $u$ with the corresponding vertices in $S'_1$. Similarly, we have 
$$\vol(S'_1) \leq \vol(B_u(2l)) \leq \vol(G)/2.$$
This implies 
$\vol(S_1)+\vol(S_2) = (\vol(G)-\vol(S'_1)+(\vol(G)-\vol(S'_2) \leq \vol(G)$
which is impossible. Therefore we conclude that the maximum flow is  of value $\vol(G)$. 

Let $F $ denote the flow achieving the flow value $\vol(G)$.  We set $\beta_{u,v}= F(u_1,v_2)$ where $u_1$ and $v_2$ are associated nodes in $V_1$ and $V_2$, respectively.
For each $u_1$ in $V_1$, we have
\[ d_{u} =c(s, u_1) = F(s,u_1)= \sum_{v_2 \in V_2} F(u_1, v_2) = \sum_{u} \beta_{u,v}. \]
Claim C is proved.

Now we are ready to prove Theorem \ref{t1}.



\begin{cor}\label{co1}
In a connected graph with girth $\gamma$, the first non-trivial eigenvalue  $\lambda_{1}$ satisfies
\begin{align}
\label{20}
\lambda_{1} & \geq 1- \Big[\frac{ 2 \sqrt{d_v-1}}{d_v}\Big]^{(2)} _{v \in V} \Big(1- \frac c {\gamma}\Big).
\end{align} 
\end{cor}
The proof is almost identical to that of Theorem \ref{t1} using the fact that in a graph with girth $\gamma$  any ball $N_u(l)$ for $l \leq \gamma/2$ has 2-volume 
}
\section{A lower bound for  $\lambda_{n-1}$}\label{sec4}
If a graph is  bipartite,  it is known (see \cite{ch0}) that $\lambda_i = 2-\lambda_{n-i-1}$  for all $0 \leq i \leq n-1$ and, in particular,
$\lambda_{n-1}=2-\lambda_0=2$. If  $G$ is not bipartite, it is easy to derive the following  lower bound:  
$$\lambda_{n-1} \geq 1+ 1/(n-1)$$ by using the fact that the trace of $\mathcal L$ is $n$.
This lower bound is sharp for the complete graph. However if $G$ is not the complete graph, is it possible to derive a better lower bound? The answer is affirmative. Here
we  give 
 an improved lower bound for $\lambda_{n-1}$. 

\begin{theorem}\label{t2}
In a connected graph $G=(V,E)$ with diameter $k$, the largest eigenvalue  $\lambda_{n-1}$ of the normalized Laplacian $\mathcal L$ of $G$ satisfies
\begin{align}
\label{20}
\lambda_{n-1} & \geq 1+ \sigma \Big(1- \frac c {k}\Big)
\end{align} 
where $\sigma$ is as defined in (\ref{sigma}), provided  $k \geq c' \log \sigma^{-1}$ and $\vol(G) \geq c'' \sigma^{\log \sigma}$ for some absolute constants $c$'s. 
\end{theorem}


\begin{proof}
By definition, $\lambda_{n-1}$ satisfies
\begin{align}
\lambda_{n-1}  &\geq \frac{\sum_{x \sim y} (f(x)-f(y))^2}{\sum_x f^2(x) d_x } = R(f)
\label{Rf}
\end{align}
for any $f : V \rightarrow {\mathbb R} $.

We will construct an appropriate $f$ such that $R(f) \geq 1+\sigma (1-  c/\gamma)$ by  considering the following function $f_u: V \rightarrow {\mathbb R}^+$, for a fixed vertex $u$, defined by
\begin{align*}
\eta_u(x)&= \begin{cases}(-1)^t \chi_u  \big(\tilde P_t (x) \big)^{-1/2}~~& \mbox{if } \text{dist}(u,x) = t \leq l \\
0 &\mbox{otherwise}
\end{cases}
\end{align*} 
where $l \leq \gamma/2$.
Note that $|\eta_u(x)| = g_u(x)$ since we assume that $l \leq \gamma/2$.  Using the same proof in Claim A, we have

\vspace{.1in}
\noindent
{\it Claim A':} 
\begin{align*}
\sum_u d_u \sum_x \eta_u^2(x)d_x &=\sum_{j=0}^l \sum_x\sum\limits_{{\mathbf p}\in \mathscr{P}^{(l)}_{u,x}} d_u w({\mathbf p}) d_x= (l+1) \sum_x d_x^2.
\end{align*}

\vspace{.1in}
\noindent
{\it Claim B':} 
\begin{align*}
\sum_u d_u \sum_{x \sim y} \big(\eta_u(x)-\eta_u(y)\big)^2 &\geq  (l+1+l\sigma) \sum_x d_x^2.
\end{align*}

\vspace{.1in}
\noindent
{\it Proof of Claim B':}
The proof is quite similar to that of Claim B.
For a fixed vertex $u$,  the sum over unordered pair $\{x,y\}$ where $x \sim y$, 
\begin{align*}
&\sum_{x \sim y} \big(\eta_u(x) -\eta_u(y)\big)^2\\
&\leq \sum_{t \leq l-1}\sum_{r \in V}\sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,r}\\{\mathbf p}'= {\mathbf p} \cup s \in \mathscr{P}^{(t+1)}_{u,s}}}
\left(\sqrt{w({\mathbf p})} +\sqrt{w({\mathbf p}')       } \right)^2 
- \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} {w({\mathbf p})}(d_x-1)\\
&\leq \sum_{t \leq l-1}\sum_x \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x}}}
\left(\sqrt{w({\mathbf p})} +\sqrt{\frac{w({\mathbf p})}{d_x-1}         } \right)^2 (d_x-1)
- \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} \sqrt{w({\mathbf p})}(d_x-1)\\
&\leq \sum_{t \leq l-1}\sum_x \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x}}}
w({\mathbf p}) \Big(1+ \frac 1 {d_x-1}+\frac 2 {\sqrt{d_x-1}}\Big)(d_x-1)
- \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} w({\mathbf p})(d_x-1)\\
&\leq \sum_{t \leq l-1}\sum_x \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x}}}
w({\mathbf p}) \Big(d_x +2\sqrt{d_x-1}\Big)
-\sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} w({\mathbf p})(d_x-1).
\end{align*}

Using Fact 3, we have
\begin{align*}
&\sum_u d_u \sum_{x \sim y} \big(\eta_u(x) -\eta_u(y)\big)^2\\
&\geq \sum_{t \leq l-1} \sum_u d_u \sum_{\substack{{\mathbf p} \in \mathscr{P}^{(t)}_{u,x}}}
w({\mathbf p}) \Big(d_x +2\sqrt{d_x-1}\Big)
- \sum_u d_u \sum_{{\mathbf p} \in \mathscr{P}^{(l)}_{u,x}} w({\mathbf p})(d_x-1)\\
&= l \sum_x d_x\big(d_x+2\sqrt{d_x-1}\big)- \sum_x d_x^2\\
&= l (1+\sigma) \sum_x d_x^2 - \sum_x d_x^2\\
&=\big(l-1+l \sigma \big) \sum_x d_x^2
\end{align*}
This proves Claim B'.


Combining Claims A' and B', we have
\begin{align}
&\sum_u d_u \sum_{x \sim y} \big(\eta_u(x) -\eta_u(y)\big)^2 \nonumber\\
&\geq \big(l-1+l \sigma \big) \sum_x d_x^2\nonumber\\
&\geq \big(l-1+l \sigma \big)\Big(\frac 1 {l+1}\Big) \sum_u d_u\sum_x \eta^2_u(x) d_x\nonumber\\
&=\Big(1+\frac {l\sigma }{l-1}\Big)\sum_u d_u\sum_x \eta^2_u(x) d_x \label{AB}
\end{align}
Thus we deduce that there is a vertex $u$ such that
\begin{align}
R(\eta_u)&= \frac {\sum_{x \sim y} \big(\eta_u(x) -\eta_u(y)\big)^2}{\sum_x \eta^2_u(x) d_x} \nonumber\\
& \leq 1+\frac {l\sigma }{l-1}.\label{e12}
\end{align}


We consider the function $\eta'_u$ defined by
\begin{align*}
\eta'_u(x) ={\eta_u(x)}- \alpha_u
\end{align*}
where 
\begin{align*}
\alpha_{v} = \frac{\sum_x \eta_v(x) d_x}{\sum_{x } d_x}=  \frac{\sum_x \eta_v(x) d_x}{\vol(G)}
\end{align*}
so that  $\eta'_u$ satisfies the condition that
\begin{align*}
\sum_x \eta'_u(x) d_x& = 0
\end{align*}
Hence, we have
\begin{align*}
\lambda_{n-1}  \geq R(\eta'_u)
&= \frac{\sum_{x \sim y} \big(\eta'_u(x)-\eta'_u(y)\big)^2}{\sum_x {\eta'}_u^2(x)d_x} \nonumber\\
&=\frac{\sum_{x \sim y} \big(\eta_u(x)-\eta_u(y)\big)^2}{\sum_x \eta_u^2(x)d_x- \alpha_u^2 {\vol(G)}}  \\
 & \geq  1+ \sigma (1+\frac c l) - \frac{\vol(B_u(l))}{\vol(G)}.
 \end{align*}
This completes the proof of Theorem \ref{t2}.
\end{proof}


\begin{thebibliography}{99}

\bibitem{loss}
M. Capalbo, O. Reingold, S. Vadhan and A. Wigderson.  Randomness conductors and constant-degree lossless expanders, {\it Proceedings of the 34th Annual ACM symposium on Theory of Computing}, 659--668, 2002.
\bibitem{ch0}
F. Chung, {\it Spectral Graph Theory},
 AMS Publications,  vii+207 pages, 1997.
 \bibitem{f}
 J. Friedman, {\it A proof of Alon's second eigenvalue conjecture and related problems}, Mem. Amer. Math. Soc., {\bf 195}, viii+100 pages, 2008.
 \bibitem{kahale}
 N. Kahale, Eigenvalues and expansion of regular graphs, {\it JACM},  { 42} (5): 1091--1106, 1995.
  \bibitem{hall}
  P. Hall, On representatives of subsets, {\it J. London Math. Soc.} {10} (1): 26--30, 1935.
 \bibitem{hoo}
 S. Hoory, A lower bound on the spectral radius of the universal cover of a graph, {\it J. Combin. Theory B},
  93: 33--43, 2005.

 \bibitem{hlw}
 S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, {\it Bull. Amer. Math. Soc.}, 
43: 439--561, 2006.
 
\bibitem{ab}
A. Nilli, On the second eigenvalue of a graph, {\it Discrete Math.},  91: 207--210, 1991.

\bibitem{tanner}
R. M. Tanner, Explicit construction of concentrators from generalized $n$-gons, {\it SIAM J. Algebraic Discrete Methods,} 5: 287--294, 1984. 
\bibitem{young}
S. J. Young, The weighted spectrum of the universal cover and an Alon-Boppana result for the normalized Laplacian, preprint.

\end{thebibliography}

\newpage

\textbf{\large Corrigendum -- added 3th November 2017}

\begin{enumerate}
\item
In the abstract, line 6-8,  the statement of the main result  should be replaced by
 \begin{align*}
 \lambda_1 \leq 1-\sigma  \big(1- \frac 5 {k} \big)
 \end{align*}
 provided  $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2  \leq 1/2$ and $ k (1.5)^k  \geq \sigma^{-1}$ where $d_v$ denotes the degree of the vertex $v$ with minimum degree at least $2$. 

Also, page 12, line -3 to -1, the statement of Theorem 9 should be similarly replaced as above.
\item
Page 3, line 13, the constant $c$ should be replaced by $5$. 
\item Page 9, line -9.  ``\ldots\  for some constant $c$." should be replaced by ``\ldots\  for  $c= 1/\log 1.5$."
\item Page 9, line -6.  Replace ``\ldots\  largest  \ldots"  by  "\ldots\   least  \ldots".

\item Page 10, line 3,  $\bar{s}_j$ should be replaced by $\bar{s}_{j+1}$.
\item Page 3, line 7 to 11. Delete ``We set  \ldots\   as defined in (15)." Note that  $\epsilon$ was defined later near the end of the proof of Theorem 9.
\item Page 16, line -6, replace ``\ldots\ using (35), \ldots"  by ``\ldots\ using (27), \ldots".
\item Page 16, line -3. Replace `` $c/(l+1)$" by ``$5/k$".  
\item Page 16, line -2. Replace `` \ldots\ the choice of $\epsilon = \sigma/k.$ " by `` \ldots\ the choice of $\epsilon = \sigma/k$ which  satisfies
$k \geq (\log \epsilon^{-1})/ \log 1.5.$" 
\item Page 17, line 11 to line 13,  the statement of Theorem 10 should be replaced by
 \begin{align*}
 \lambda_{n-1} \geq 1+\sigma  \big(1- \frac 5 {k} \big)
 \end{align*}
 provided  $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2  \leq 1/2$ and $ k (1.5)^k  \geq \sigma^{-1}$ where $d_v$ denotes the degree of the vertex $v$ with minimum degree at least $2$. 


\end{enumerate}



\end{document}
