\documentclass[12pt]{article} \usepackage{e-jc} % we recommend these ams packages \usepackage{amsthm,amsmath,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}{June 22, 2016}\\ \small Mathematics Subject Classifications: 05C50} \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})}. \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} \end{document}