\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P27}{20(4)}{2013}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\allowdisplaybreaks

% declare theorem-like environments
\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}

\newcommand{\G}{{\mathcal G}}
\newcommand{\tr}{{\rm Trace}}
\newcommand{\E}{{\mathrm E}}
\newcommand{\Var}{{\rm Var}}
\newcommand{\Cov}{{\rm Cov}}
\newcommand{\vol}{{\rm vol}}

\title{\bf Spectra of edge-independent random graphs}
 \author{Linyuan Lu
 \thanks{This author was supported in part by NSF
grant DMS 1000475, DMS 1300547, and ONR grant N00014-13-1-0717. }\\
\small Mathematics Department\\[-0.8ex]
\small The University of South Carolina\\[-0.8ex]
\small Columbia, SC, USA  \\
\small\tt lu@math.sc.edu\\ 
   \and Xing Peng\\
\small Mathematics Department\\[-0.8ex]
\small The University of California, San Diego\\[-0.8ex]
\small La Jolla, CA, USA  \\
\small\tt x2peng@ucsd.edu
} 

% \thanks{University of South Carolina, Columbia, SC 29208,
% ({\tt pengx@mailbox.sc.edu}).This author was supported  by the Dean's Dissertation Fellowship of College of Arts and Sciences. }}

% \author{Linyuan Lu
% \thanks{University of South Carolina, Columbia, SC 29208,
% ({\tt lu@math.sc.edu}). This author was supported in part by NSF
% grant DMS 1000475. }
%   \and Xing Peng
% \thanks{University of South Carolina, Columbia, SC 29208,
% ({\tt pengx@mailbox.sc.edu}).This author was supported  by the
% Dean's Dissertation Fellowship of College of Arts and Sciences. }}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{July 12, 2013}{Nov 17, 2013}{Nov 29, 2013}\\
\small Mathematics Subject Classifications: 05C80, 05D40, 15A18}


\begin{document}
\maketitle


\begin{abstract}
  Let $G$ be a random graph on the vertex set $\{1,2,\ldots, n\}$ such
  that edges in $G$ are determined by independent random indicator
  variables, while the probabilities $p_{ij}$ for $\{i,j\}$ being an
  edge in $G$ are not assumed to be equal. Spectra of the adjacency
  matrix and the normalized Laplacian matrix of $G$ are recently
  studied by Oliveira and Chung-Radcliffe. Let $A$ be the adjacency
  matrix of $G$, $\bar A={\rm E}(A)$, and $\Delta$ be the maximum expected
  degree of $G$.  Oliveira first proved that asymptotically almost surely $\|A-\bar
  A\|=O(\sqrt{\Delta \ln n})$ provided $\Delta\geq C \ln n$ for some
  constant $C$. Chung-Radcliffe improved the hidden constant in the
  error term using a new Chernoff-type inequality for random matrices.
  Here we prove that asymptotically almost surely $\|A-\bar A\|\leq
  (2+o(1))\sqrt{\Delta}$ with a slightly stronger condition $\Delta\gg
  \ln^4 n$.  For the Laplacian matrix $L$ of $G$, Oliveira and
  Chung-Radcliffe proved similar results $\|L-\bar L\|=O(\sqrt{\ln
    n}/\sqrt{\delta})$ provided the minimum expected degree
  $\delta\geq C' \ln n$ for some constant $C'$; we also improve their results by removing the
  $\sqrt{\ln n}$ multiplicative factor from the error term under some mild
  conditions. Our results naturally apply to the classical
  Erd\H{o}s-R\'enyi random graphs, random graphs with given expected
  degree sequences, and bond percolation of general graphs.

% keywords are optional
  \bigskip\noindent \textbf{Keywords:} edge-independent random graphs;
  random symmetric matrices; eigenvalues; Laplacian eigenvalues; trace method.
\end{abstract}


\section{Introduction}
Given an $n \times n$ symmetric matrix $M$, let $\lambda_1(M)$,
$\lambda_2(M),\ldots, \lambda_n(M)$ be  eigenvalues of $M$
in the non-decreasing order. What can we say about these eigenvalues
if $M$ is a matrix associated with a random graph $G$? Here $M$ could be
the adjacency matrix (denoted by $A$) or the normalized Laplacian
matrix (denoted by $L$). Both spectra of $A$ and $L$ can be used to
deduce  structures of $G$. For example, the spectrum of $A$ is
related to the chromatic number and the independence number.  The
spectrum of $L$ is connected to the mixing-rate of random walks, the
diameters, the neighborhood expansion, the Cheeger constant, the
isoperimetric inequalities, and the expander graphs. For more applications of spectra of the adjacency matrix and the Laplacian matrix, please refer to the monographs  \cite{fan4,cv}.




% In the literature there are many results on the spectra of random
% graphs and random matrices.
%  In a typical senario, the entries $M_{ij}$
% are often assumed to be independent random variables. Some assume that
% all $M_{ij}$ have identical distributions while others assume a weaker
% condition. For example, Wigner proved the spectra of $M$ follows the
% Semi-Circle Law if in addition all entries $M_{ij}$ have an identical
% expected value and an identical variance.


Spectra of adjacency matrices and  normalized Laplacian
matrices of random graphs were extensively investigated in the
literature. For the Erd\H{o}s-R\'enyi random graph model $G(n,p)$,
F\"uredi and Koml{\'o}s \cite{fk} proved the following. If  $np(1-p)\gg \ln^6 n$, then asymptotically almost surely
\[
\lambda_n(A)=(1+o(1))np  \textrm{ and }  \max_{i \leq
  n-1}|\lambda_i(A)|\leq (2+o(1))\sqrt{np(1-p)}.\]
Here the notation $o(1)$ means a quantity goes to $0$ as $n$
goes to infinity. In this paper, we always consider the sequence of
graphs $\{G_n\}$ where $n$ is the number of vertices.
Similar results are proved for sparse random graphs \cite{fo,ks} and general random matrices \cite{dj,fk}.
 Tropp \cite{tropp} proved  probability inequalities for sums of independent,
random, self-adjoint matrices.
Alon,
Krivelevich, and Vu \cite{akv} showed that with high probability the
$s$-th largest eigenvalue of a random symmetric matrix with
independent random entries of absolute value at most one concentrates
around its median. Chung, Lu, and Vu \cite{flv1,flv2} studied spectra
of adjacency matrices of random power law graphs and spectra of
Laplacian matrices of random graphs with given expected degree
sequences. Their results on random graphs with given expected degree
sequences were complemented by Coja-Oghlan \cite{og,o} for sparser
cases.  For random $d$-regular graphs, Friedman (in a series of papers)
\cite{fks,friedman,friedman2} proved that  the   second largest
eigenvalue (in absolute value) of random $d$-regular graphs is at most  $(2 + o(1))
\sqrt{d-1}$ asymptotically almost surely  for any $d \geq 4$.


In this paper, we study spectra of the adjacency matrices and the
 Laplacian matrices of edge-independent random graphs.  Let $G$ be an
edge-independent random graph on the vertex set
$[n]:=\{1,2,\ldots,n\}$; two vertices $i$ and $j$ are adjacent in $G$ independently
with probability $p_{ij}$. Here $p_{ij}=p_{ji}$ since edges are
unoriented and the diagnals $p_{i,i}$ is not always required to zero.
 Here $\{p_{ij}\}_{1\leq i,j \leq n}$ are not assumed to be equal.  Let $\bar A:=(p_{ij})_{i,j=1}^n$ be the
expectation of the adjacency matrix $A$ and
%$\Delta=\max_i\{\sum_{j=1}^n p_{ij}\}$
$\Delta$ be the maximum expected degree of $G$. Oliveira \cite{oli}
proved $\|A-\bar A\|=O(\sqrt{\Delta \ln n})$ provided $\Delta\geq C\ln
n$ for some constant $C$.  Chung and Radcliffe \cite{fan7}
improved the hidden constant in the error term  using a Chernoff-type inequality
for random matrices.  We manage to remove the $\sqrt{\ln n}$ factor
from the error term with a slightly stronger assumption on $\Delta$.  For two functions $f(x)$ and $g(x)$ taking nonnegative values, we say $f(x) \gg g(x)$ (or $g(x)=o(f(x))$) if $\lim_{x \to \infty} \tfrac{g(x)}{f(x)}=0$.
We have the following theorem.
\begin{theorem} \label{thm:1}
Consider an edge-independent random graph $G$.
%Let $\bar A$  and $\Delta$ defined above.
If $\Delta \gg \ln^4 n$, then asymptotically almost surely
$$
|\lambda_i(A)-\lambda_i(\bar A) |\leq (2+o(1)) \sqrt{\Delta}
$$
for each $1 \leq i \leq n$.
\end{theorem}

Note that the bound $(2+o(1))\sqrt{\Delta}$ is best possible by the
following observation. For Erd\H{o}s-Renyi random graphs $G(n,p)$,
it has been shown \cite{fk} that the eigenvalues follows the semi-circular law of radius
$(2+o(1))\sqrt{np}$ as $np(1-p)\to \infty$. In particular,
there are many eigenvalues in the interval $((2-\epsilon)\sqrt{np}, (2+\epsilon)\sqrt{np})$. 
But all eigenvalues of $\bar A$, except the largest one,  is $-p$. 
We conjecture that Theorem \ref{thm:1} holds as long as $\Delta\gg \ln n$
but the current approaches requires $\Delta \gg \ln^4 n$. 


Let $T$ be the diagonal matrix of expected degrees.
Define $\bar L=I - T^{-1/2}\bar A T^{-1/2}$. The matrix $\bar L$ can be viewed
as the ``expected Laplacian'' of $G$ rather than the entrywise expectation of $L$.   Oliveira \cite{oli} and Chung-Radcliffe \cite{fan7} proved  theorems   on $L$ which are similar to those on  the adjacency matrix $A$. We are able to improve their results by removing  the $\sqrt{\ln n}$ factor from the error term with some conditions.
We say  $\bar L$ is  well-approximated by a rank-$k$ matrix if
there is a $k$ such that all but $k$ eigenvalues
$\lambda_i(\bar L)$ satisfy $|1-\lambda_i(\bar L)|=o(1/\sqrt{\ln n})$.
To make the definition rigorous,
let  $$\Lambda:=\{\lambda_i(\bar L)\colon  |1-\lambda_i(\bar L)| \geq 1/(g(n)\sqrt{\ln n})\},$$
where $g(n)$ is an arbitrarily slowly growing function such that $g(n)\to \infty$ as $n \to \infty$; then we have $k:=|\Lambda|$. We have the following theorem.

%  We relabel the eigenvalues of
% $\bar L$ such that $|1-\mu_1'| \geq |1-\mu_2'|\geq \cdots \geq
% |1-\mu_n'| $. Let $k$ be the first integer such that
% $|1-\mu_i'|=o(1/\sqrt{\ln n})$ for all $k+1 \leq i \leq n$.
% Equivalently, $|1-\mu_i'|=\Omega(1/\sqrt{\ln n})$ for each $1 \leq i
% \leq k$. Furthermore, let $k' \leq k$ be the first integer with
% $|1-\mu_i'|=o(1)$ for each $k'+1 \leq i \leq n$. We have the
% following theorem.
\begin{theorem} \label{thm:2} Consider an edge-independent random
  graph $G$.  Let $\Lambda$ and $k$ be
defined above. If the minimum expected degree $\delta$ satisfies $\delta\gg  \max\{k, \ln^4 n\}$, then asymptotically almost surely,
$$
| \lambda_i(L)-\lambda_i(\bar L) |\leq \left(2+\sqrt{\sum_{\lambda\in \Lambda}(1-\lambda)^2}+o(1)\right)\frac{1}{\sqrt{\delta}}$$
for each $1 \leq i \leq n$.
\end{theorem}

The rank condition is due to the discrepancy of degrees (see the proof
of Lemma \ref{l:M4}). We think that this condition is unnecessary but
we fail to remove it.
Note   ${\rm rank}(I-\bar L)={\rm rank}(\bar A)$. We have the following corollary.
\begin{corollary} \label{cor:1}
 Consider an edge-independent random graph $G$ with ${\rm rank}(\bar A)=k$.
 If the minimum expected degree $\delta$ satisfies $\delta\gg  \max\{k, \ln^4 n\}$, then asymptotically almost surely,
 we have  $$
| \lambda_i(L)-\lambda_i(\bar L) |\leq \frac{2+\sqrt{k}+o(1)}{\sqrt{\delta}}$$
for $1\leq i \leq n$.
\end{corollary}

A special case is the  random graph $G({\mathbf w})$ with given  expected degree sequence
${\mathbf w}=(w_1, w_2, \ldots,w_n)$, where $v_iv_j$ is an edge independently with
probability $p_{ij}=\frac{w_iw_j}{\sum_{l=1}^nw_l}.$
Let $\delta=w_{\min}$ and
$\bar w=\frac{\sum_{i=1}^n w_i}{n}$.
Chung-Lu-Vu  \cite{flv2} proved that if  $\delta\gg \sqrt{\bar w} \ln^3 n$,  then for each non-trivial eigenvalue $ \lambda_i(L)$, we have
\begin{equation}
  \label{eq:gw}
  |1- \lambda_i(L)|\leq  \frac{4+o(1)}{\sqrt{\bar w}}.
\end{equation}

Note that in this case $I-{\bar L}=T^{-1/2}\bar AT^{-1/2}$;
its $(i,j)$-entry is given by $\frac{\sqrt{w_iw_j}}{\sum_{l=1}^nw_l}$.
Thus $I-{\bar L}$ is a rank-1 matrix with non-zero eigenvalues equal 1.
Hence all non-trivial eigenvalues of $\bar L$ are $1$. Applying  Corollary \ref{cor:1},
we get
\begin{equation}
  \label{eq:gw2}
  |1- \lambda_i(L)|\leq  \frac{3+o(1)}{\sqrt{\delta}},
\end{equation}
provided $\delta\gg \ln^4 n$.

In comparison to inequality \eqref{eq:gw}, inequality \eqref{eq:gw2} improves the constant and requires a weaker condition. However, the bounds from inequalities \eqref{eq:gw} and \eqref{eq:gw2} are incomparable in general.


Here is another application.
Let $G$ be a host graph with the vertex set $[n]$. The bond percolation of $G$ (with probability $p$)
is a random spanning subgraph $G_p$ of $G$ such that for each edge $\{i,j\}$ of $G$,
$\{i,j\}$ is retained as an edge of $G_p$ independently with probability $p$.
The Erd\H{o}s-R\'enyi graph $G(n,p)$ can be viewed as the  bond percolation
of the complete graph $K_n$. We have the following theorems on the spectrum of $G_p$ for a general graph $G$.

\begin{theorem}
Suppose that the maximum degree $\Delta$ of $G$ satisfies $\Delta\gg \ln^4 n$.
For $p\gg \frac{\ln^4n}{\Delta}$, asymptotically almost surely we have
$$|\lambda_i(A(G_p))-p\lambda_i(A(G))|\leq (2+o(1))\sqrt{p\Delta}$$
for $1 \leq i \leq n$.
\end{theorem}

\begin{theorem}
Suppose that all but $k$ Laplacian eigenvalues $\lambda$ of $G$
satisfies $|1-\lambda|=o(\frac{1}{\sqrt{\ln n}})$.
If the minimum degree $\delta$ of $G$ satisfies $\delta\gg \max\{k,\ln^4 n\}$,
then for $p\gg \max\{\frac{k}{\delta},\frac{\ln^4n}{\delta}\}$, asymptotically almost surely we have
$$|\lambda_i(L(G_p))-\lambda_i(L(G))|\leq
\left(2+\sqrt{\sum_{i=1}^k (1-\lambda_i)^2}+o(1))\right)\frac{1}{\sqrt{p\delta}},$$
for $1 \leq i \leq n$. Where $\lambda_1, \ldots, \lambda_k$ are those $k$ Laplacian eigenvalues of $G$ which do not satisfy
$|1-\lambda|=o(\frac{1}{\sqrt{\ln n}})$.
\end{theorem}

The rest of the paper is organized as follows. In section 2, we will
generalize Vu's result  \cite{vu} on the spectral
bound of a random symmetric matrix; we use it to prove theorem \ref{thm:1}.
In section 3, we will prove several lemmas for  Laplacians. Finally,
 Theorem \ref{thm:2} will be proved in Section 4.

\section{Spectral bound of random symmetric matrices}
For each matrix $M$, the {\em spectral norm} $\|M\|$ is the largest singular value of $M$; i.e., we have
$$\|M\| =\sqrt{\lambda_{max}(M^*M)}.$$
Here $M^*$ is the conjugate transpose of $M$ and $\lambda_{max}(\cdot)$
is the largest eigenvalue. When $M$ is an $n \times n$ symmetric matrix, we have
$\|M\|=\max \{|\lambda_i(M)| \colon 1 \leq i \leq n\}.$

We will estimate the spectral norm of
random symmetric  matrices. Let us start with the following theorem proved by Vu in \cite{vu}.

\begin{theorem} \label{thm:vu}
There are constants $C$ and $C'$ such that
the following holds. Let $b_{  ij}$, $1\leq i\leq j \leq n$ be independent
random variables, each of which has mean $0$ and variance at most $\sigma^2$
and is bounded in absolute value by $K$, where $\sigma\geq C'n^{-1/2}K\ln^2n$.
Then asymptotically almost surely
\begin{equation}
  \label{eq:vu}
\|B\|\leq 2\sigma\sqrt{n}+C(K\sigma)^{1/2}n^{1/4}\ln n.
\end{equation}
\end{theorem}

Vu's theorem is already in a very general form; it improves F\"uredi-Koml{\'o}s's result \cite{fk} on $G(n,p)$.  When we consider an edge-independent random graph $G$, let $A$ be the adjacency matrix of $G$ and $\bar A$ be the expectation of $A$.
If we apply Theorem \ref{thm:vu} to $B:=A-\bar A$, we get
\begin{equation} \label{eq:vu1}
\|A-\bar A\|\leq 2\sigma\sqrt{n}+C(\sigma)^{1/2}n^{1/4}\ln n,
\end{equation}
where $\sigma=\max_{1\leq i\leq j \leq n}\{\sqrt{p_{ij}(1-p_{ij})}\}$.
The upper bound in inequality \eqref{eq:vu1} is weaker than the one in Theorem \ref{thm:1}; this is because the uniform bounds on
$K$ and $\sigma^2$ are too coarse.

To overcome the deficiency, we assume that $b_{ij}$ ($1\leq i \leq j\leq n$) are independent random variables with the
following properties:
\begin{itemize}
\item $|b_{ij}|\leq K$ for $1\leq i<j\leq n$;
\item $\E(b_{ij})=0$, for all $1\leq i<j\leq n$;
\item $\Var(b_{ij})\leq \sigma_{ij}^2$.
\end{itemize}
If $i>j$, we set
 $b_{ji}=b_{ij}$.
Consider a random  symmetric  matrix $B=(b_{ij})_{i,j=1}^n$.
%The spectrum norm of $B$, denoted by $\|B\|$, is the largest absolute
%eigenvalue of $B$. We have the following theorem.
The following theorem generalizes Vu's theorem.

\begin{theorem}\label{thm:3}
There are constants $C$ and $C'$ such that the following holds.
  Let $B$ be a random symmetric  matrix defined above and
  $\Delta=\max_{1\leq i\leq n}\sum_{j=1}^n\sigma_{ij}^2$.  If $\Delta\geq C' K^2 \ln^4 n$,
then asymptotically almost surely
\begin{equation}
  \label{eq:B}
  \|B\|\leq 2\sqrt{\Delta} + C \sqrt{K} \Delta^{1/4}\ln n.
\end{equation}
\end{theorem}
When $\sigma_{ij}\equiv \sigma$, we have
$\Delta=n\sigma^2$. Thus, inequality \eqref{eq:B} implies
inequality \eqref{eq:vu}. (The condition $\Delta\geq C' K^2 \ln^4 n$
becomes $\sigma\geq \sqrt{C'}n^{-1/2}K\ln^2 n$.)

Replacing $B$ by $cB$, $K$ by $cK$, and $\Delta$ by $c\Delta$,  inequality \eqref{eq:B} is invariant under scaling. Without loss of generality,
we can assume  $K=1$ (by scaling a factor  of $\frac{1}{K}$).
We further assume that  diagonal entries are zeros.
Changing  diagonal entries to zeros can affect the spectral norm by at most $K$,
which is negligible in comparison to the upper bound.

We use Wigner's trace method \cite{wigner}. We have
\begin{equation}
  \label{eq:tr1}
\E\left(\tr(B^k)\right)=\sum_{i_1,i_2,\ldots, i_k} \E(b_{i_1 i_2}
b_{i_2 i_3} \ldots b_{i_{k-1} i_{k}}b_{i_k i_1}).
\end{equation}


Each sequence $w:=i_1 i_2 \ldots i_{k-1}i_k i_1$ is a {\it closed
walk} of length $k$ in the complete graph $K_n$.
Let $E(w)$
 be the set of edges appearing in $w$.
For each edge $e\in E(w)$, let $q_e$ be the number of occurrence
of the edge $e$ in the walk $w$.
By the independence assumption for edges, we can rewrite equation \eqref{eq:tr1} as
\begin{equation}
  \label{eq:tr2}
\E\left(\tr(B^k)\right)=\sum_{w} \prod_{e\in E(w)} \E(b^{q_e}_e).
\end{equation}
Here the summation is taken over all closed walks of length $k$.
If $q_e=1$ for some $e\in E(w)$, then $\prod_{e\in E(w)} \E(c^{q_e}_e)=0$.
% If there is some $j$ such that the edge $i_{j} i_{j+1}$ appears
% once, then  we have
% $$\E(C_{i_1 i_2}
% C_{i_2 i_3} \ldots C_{i_{t-1} i_{t}}C_{i_t i_1})=\E(C_{i_1 i_2} C_{i_2 i_3} \ldots C_{i_{j-1} i_{j}}
% C_{i_{j+1}i_{j+1}} \ldots  C_{i_{t-1} i_{t}}C_{i_t i_1}) \E(C_{i_j
% i_{j+1}})=0$$ by recalling $\E(C_{ij})=0$.
Thus we need only to
consider all closed walks such that each edge appears at least twice.

A closed walk $w$ is {\em good} if each edge in $E(w)$
occurs more than once. The set of all good closed walks  of length $k$ in $K_n$
is denoted by ${\mathcal G}(n,k)$.
% A good closed walk $w$ of length $k$ can contain at most
% $\lfloor \frac{k}{2} \rfloor$ distinct edges. For $1 \leq i \leq
% \lfloor\frac{k}{2} \rfloor$, let ${\mathcal G}_i(n,k)$ be the set of all
% good closed walks with $i$ distinct edges.
%  Thus we have
% \begin{equation}\label{eq:power}
% \E(\tr(B^t))= \sum_{i=1}^{\lfloor \frac{k}{2}\rfloor} \sum_{w \in
% {\mathcal G}_i(n,k)} \prod_{e \in E(w)} \E(c_e^{q_e}).
% \end{equation}
% %where $\sum_{e \in E(w)}n_e=t$.

Since $q_e\geq 2$ and $|b_e|\leq 1$, we have
\begin{equation}
  \label{eq:be}
|\E(b_e^{q_e})|\leq  \E(b_e^{2}) =\Var(b_e^2)\leq \sigma_{e}^2.
\end{equation}

Putting equation \eqref{eq:tr2} and inequality \eqref{eq:be} together, we have
\begin{equation}
  \label{eq:bk}
\left |\E\left(\tr(B^k)\right)\right |\leq \sum_{w\in {\G(n,k)}}
 \prod_{e\in E(w)}   \sigma_e^2.
\end{equation}

Let $\G(n,k,p)$ be the set of good closed walks in $K_n$ of length $k$ and
with $p$ vertices. The key of the trace method is a good estimate
on $|\G(n,k,p)|$.
F\"uredi and Koml{\'o}s \cite{fk} proved
\begin{equation}
  \label{eq:fk}
  |\G(n,k,p)|\leq n(n-1)\cdots (n-p+1) \frac{1}{p}{2p-2 \choose p-1}
{k \choose 2p-2} p^{2(k-2p+2)}.
\end{equation}

Let $\tilde \G(k,p)$ be the set of good closed walks $w$ of length $k$
on the complete graph $K_p$
where vertices first appear in $w$ in the order $1,2,\ldots, p$. It is easy
to check $|\G(n,k,p)|= n(n-1)\cdots (n-p+1)|\tilde \G(k,p)|$.
The main contribution from Vu's paper \cite{vu} is the following  bound
(see \cite{vu}, Lemma 4.1):
\begin{equation}
 \label{eq:vub}
|\tilde \G(k,p)| \leq {k \choose 2p-2} 2^{2k-2p+3} p^{k-2p+2}(k-2p+4)^{k-2p+2}.
\end{equation}
It improves F\"uredi-Koml{\'o}s' bound \eqref{eq:fk}. (If we use
\eqref{eq:fk}, then we will get a weaker version of Theorem
\ref{thm:1}, which requires $\Delta\gg \ln^6 n$.)

We will use this bound to derive the following Lemma.

\begin{lemma} \label{trace}
For any even integer $k$ such that $k^4\leq \frac{\Delta}{32}$, we have
  \begin{equation}
    \label{eq:trace}
    \left |\E\left(\tr(B^k)\right)\right |\leq 2^{k+2}n\Delta^{k/2}.
  \end{equation}
\end{lemma}

\begin{proof}
Recall that any walks in ${\mathcal G}(n,k,p)$ can be
coded by a walk in $\tilde {\mathcal G}(k,p)$ plus the ordered
$p$ distinct vertices. Let $[n]^{\underline{p}}:=\{(v_1,v_2,\ldots,
v_p)\in
[n]^p\colon v_1,v_2,\ldots, v_p \mbox{ are distinct}\}.$
 % Let $[n]^{\underline{p}}:=\{(v_1,v_2,\ldots, v_p)\in
% [n]^p\colon v_1,v_2,\ldots, v_p \mbox{ are distinct}\}.$ Define
% $$\phi\colon {\mathcal G}(n,k,p) \to \tilde {\mathcal G}(k,p) \times
% [n]^{\underline{p}}$$ as follows.  For a good closed walk $w=i_1i_2
% \ldots i_k i_1 \in {\mathcal G}(n,k,p)$, let $v_1, v_2, \ldots, v_p$
% be the list of $p$ vertices in the order as they appear in
% $w$. Replacing $v_i$ by $i$ for $1 \leq i \leq p$, we get a good
% closed walk $\tilde w\in \tilde {\mathcal G}(k,p)$.  Now we define
% $\phi(w)=(\tilde w, (v_1,v_2,\ldots, v_p))$.  Clearly $\phi$ is a
% bijection.
Let $w=i_1i_2\ldots i_ki_1$ be a good closed walk in $\tilde {\mathcal G}(k,p)$,
we define a rooted tree $T(w)$ (with root $1$)
on the vertex set $[p]$ as follows:
$$
i_ji_{j+1} \in E(T) \ \textrm{if and only if }\ i_{j+1} \not \in \{i_1,
i_2, \ldots,i_j\}.
$$

Equivalently, the edge $i_ji_{j+1} \in E(T(w))$ if it brings in a new vertex
when it occurs first time. For $2\leq l \leq p$, let $\eta(l)$ be the parent
of $l$ in $T(w)$. Since 
Dropping those terms  $ \sigma^2_{e}$ for $e\not\in T(w)$, we get
  \begin{align*}
 \sum_{w \in {\mathcal G}(n,k,p)} \prod_{e\in E(w)} \sigma^2_e&=
 \sum_{\tilde w \in \tilde {\mathcal G}(k,p)} \sum_{(v_1,\ldots, v_p)\in [n]^{\underline{p}}}
 \prod_{xy\in E(\tilde w)} \sigma^2_{v_xv_y} \\
 &\leq  \sum_{\tilde w \in \tilde {\mathcal G}(k,p)}  \sum_{v_1=1}^n \sum_{v_2=1}^n \cdots \sum_{v_{p}=1}^n \prod_{xy\in E(T)} \sigma^2_{v_xv_y}\\
&= \sum_{\tilde w \in \tilde {\mathcal G}(k,p)} \sum_{v_1=1}^n \sum_{v_2=1}^n \cdots \sum_{v_{p}=1}^n
\prod_{y=2}^p \sigma^2_{v_{\eta(y)}v_y}\\
&=  \sum_{\tilde w \in \tilde {\mathcal G}(k,p)} \sum_{v_1=1}^n \sum_{v_2=1}^n \cdots \sum_{v_{p-1}=1}^n
\prod_{y=2}^{p-1} \sigma^2_{v_{\eta(y)}v_y} \sum_{v_p=1}^n  \sigma^2_{v_{\eta(p)}v_p}
\\
&\leq \Delta
\sum_{\tilde w \in \tilde {\mathcal G}(k,p)} \sum_{v_1=1}^n \sum_{v_2=1}^n \cdots \sum_{v_{p-1}=1}^n
\prod_{y=2}^{p-1} \sigma^2_{v_{\eta(y)}v_y}\\
 & \leq \cdots \\
& \leq \Delta^{p-1}  \sum_{\tilde w \in \tilde {\mathcal G}(k,p)}  \sum_{v_1=1}^n 1.\\
&= n \Delta^{p-1}  \left|\tilde {\mathcal G}(k,p)\right|.
\end{align*}
The main idea in above inequalities is a typical induction on trees.
Start with a leaf vertex $v_p$, bound $\sum_{v_p=1}^n \sigma^2_{v_{\eta(p)}v_p}$
by $\Delta$, and then iterate the process. Now combining it with inequality \eqref{eq:bk}, we get
\begin{align*}
  \left |\E\left(\tr(B^k)\right)\right | &\leq \sum_{w \in {\mathcal G}(n,k)} \prod_{e\in E(w)} \sigma^2_e \\
&=\sum_{p=2}^{k/2+1}\sum_{w \in {\mathcal G}(n,k)} \prod_{e\in E(w)} \sigma^2_e \\
&\leq \sum_{p=2}^{k/2+1}n \Delta^{p-1} \left|\tilde {\mathcal G}(k,p)\right|\\
&\leq n \sum_{p=2}^{k/2+1} \Delta^{p-1}  {k \choose 2p-2} 2^{2k-2p+3} p^{k-2p+2}(k-2p+4)^{k-2p+2}.
\end{align*}
In the last step, we applied Vu's bound \eqref{eq:vub}.
Let \[S(n,k,p):=n \Delta^{p-1}  {k \choose 2p-2} 2^{2k-2p+3} p^{k-2p+2}(k-2p+4)^{k-2p+2}.\]
One can show
$$S(n,k,p-1)\leq \frac{16 k^4}{\Delta}S(n,k,p).$$
%for some constant $C$ independent of $n$ and $k$.
When $k^4\leq \frac{\Delta}{32}$, we have $S(n,k,p-1)\leq \frac{1}{2}S(n,k,p)$.
Thus,
\begin{align*}
 \left |\E\left(\tr(B^k)\right)\right |
&\leq  \sum_{p=2}^{k/2+1}S(n,k,p)\\
&\leq S(n,k,k/2+1) \sum_{p=2}^{k/2+1} \left(\frac{1}{2}\right)^{k/2+1-p}\\
&<  2S(n,k,k/2+1)\\
&=n 2^{k+2}\Delta^{k/2}.
\end{align*}
The proof of this Lemma is finished.
\end{proof}



Now we are ready to prove Theorem \ref{thm:3}.

\begin{proof}[Proof of Theorem \ref{thm:3}] 
We assume $k$ is even, then we have
\begin{align*}
\Pr(\|B\|\geq  2\sqrt{\Delta} + C  \Delta^{1/4}\ln n)
&= \Pr(\|B\|^k\geq  (2\sqrt{\Delta} + C  \Delta^{1/4}\ln n)^k)   \\
&\leq \Pr(\tr(B^k) \geq  (2\sqrt{\Delta} + C \Delta^{1/4}\ln n)^k)   \\
&\leq \frac{\E(\tr(B^k))}{ (2\sqrt{\Delta} + C  \Delta^{1/4}\ln n))^k} \textrm{ (Markov's inequality)}\\
&\leq  \frac{n2^{k+2}\Delta^{k/2}}{ (2\sqrt{\Delta} + C \Delta^{1/4}\ln n))^k}\\
&= 4n e^{-(1+o(1))\frac{C}{2}k\Delta^{-1/4}\ln n}.
\end{align*}
%\hspace*{-1cm}
Setting $k$ as an even integer closest to $\left(\frac{\Delta}{32}\right)^{1/4}$, we get
$$\Pr(\|B\|\geq  2\sqrt{\Delta} + C  \Delta^{1/4}\ln n)=o(1)$$
for sufficiently large $C$.
The proof of Theorem \ref{thm:3} is finished. 
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:1}]
Let $B=A-\bar A$. Notice $|b_{ij}|\leq 1$ and
$\Var(b_{ij})=p_{ij}(1-p_{ij})\leq p_{ij}.$

Apply Theorem \ref{thm:3} to $B$ with $K=1$, $\sigma_{ij}^2=p_{ij}$,
and $\Delta=\max_{1\leq i\leq 1} \sum_{j=1}^n p_{ij}$. We get
$$\|B\|\leq 2\sqrt{\Delta}+C  \Delta^{1/4}\ln n.$$
When $\Delta\gg \ln^4 n$, we have
$$\|B\|\leq (2+o(1))\sqrt{\Delta}.$$
Applying Weyl's inequality \cite{fra}, we get
$$|\lambda_i(A)-\lambda_i(\bar A)|\leq \|A-\bar A\|\leq  (2+o(1))\sqrt{\Delta}.$$
The proof of Theorem \ref{thm:1} is completed. 
\end{proof}


\section{Lemmas for Laplacian eigenvalues}
% In  this paper, the notation $\|M\|$ means the spectral norm
%of the matrix $M$. We will use $M_{ij}$ or $M(i,j)$ to denote the
%intersection of the $i$-th row and the $j$-th column of $M$.

%For a graph $G$ with the vertex set $\{v_1,\ldots,v_n\}$,  let $A$
%be the adjacency matrix  of $G$, where $A_{ij}=1$ if $v_i \sim v_j$
%and $A_{ij}=0$ otherwise.
 %  we assume the eigenvalues of $A$ are
% listed as $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n$.
%The set $\{\lambda_1,\lambda_2,\ldots,\lambda_n\}$ is the spectra of the adjacency spectra of $G$.
%Let $L$ be the normalized Laplacian matrix
%of $G$, where
% $$L_{ij}=
 %\begin{cases}
 %1  & \ \textrm{if} \ i=j \ \mbox{and} \ d_i \not =0; \\
 %-\frac{1}{\sqrt{d_id_j}} & \ \textrm{if} \ i \not = j \ \mbox{and} \ v_i \sim v_j; \\
 %0  & \ \textrm{otherwise}.
%\end{cases}
%$$
%We assume the eigenvalues of $L$ are listed as $0=\mu_1 \leq \mu_2
%\leq  \ldots \leq \mu_n \leq 2$.
% The set $\{\mu_1,\mu_2,\ldots,\mu_n\}$ is the spectra of the Laplacian matrix of $G$.
%For properties of spectra of adjacency matrix and
%Laplacian matrix of a graph, please refer to the monographs
%\cite{fan4,cv}.

In this section, we will present some necessary lemmas  for proving Theorem \ref{thm:2}.
Recall that $G$ is an edge-independent random graph over
$[n]$ such that  $\{i,j\}$ forms as an edge independently
with probability $p_{ij}$.  For $1\leq i\leq j \leq n$, let
$X_{ij}$ be the random indicator variable for $\{i,j\}$ being an edge;
we have $\Pr(X_{ij}=1)=p_{ij}$ and $\Pr(X_{ij}=0)=1-p_{ij}$.  For each
vertex $i \in [n]$, we use $d_i$ and $t_i$ to denote the degree and
the expected degree of the vertex $i$ in $G$ respectively.
We have
$$d_i=\sum_{j=1}^n X_{ij} \ \mbox{and} \ t_i=\sum_{j=1}^n p_{ij}.
$$
  Let $D$ (and $T$) be the
diagonal matrix with $D_{ii}=d_i$  (and $T_{ii}=t_i$) respectively.
The matrix $T$ is the expectation of $D$.
Note that  we use $A$ and $L$ to denote
the adjacency matrix and the Laplacian matrix of $G$ respectively. Here
$L=I-D^{-1/2}AD^{-1/2}$.  Moreover, we let $\bar A:=\E(A)=(p_{ij})_{i,j=1}^n$ be the
expectation of $A$.
We also define $\bar L=I-T^{-1/2}\bar AT^{-1/2}$. The matrix $\bar L$ can be viewed
as the ``expected Laplacian matrix'' of $G$.


For notational convenience,   we write  eigenvalues of the expected Laplacian matrix $\bar L$ as
$\mu_1, \mu_2, \ldots, \mu_n$
such that
$$|1-\mu_1| \geq |1-\mu_2|\geq \cdots \geq |1-\mu_n|.$$
By the definition of $k$ and $\Lambda$, we have
$\Lambda=\{\mu_1, \ldots, \mu_k\}$ and $|1-
\mu_i|=o(1/\sqrt{\ln n})$ for all $i \geq k+1$.

 Let $\{\phi^{(1)}, \phi^{(2)}, \ldots, \phi^{(n)}\}$ be an orthonormal basis for the eigenspaces of $\bar L$. Note  $\bar L \phi^{(i)}= \mu_i \phi^{(i)}$ and  $  T^{-1/2}\bar AT^{-1/2} \phi^{(i)}=(1-\mu_i) \phi^{(i)}$ for  $1 \leq i \leq n$.
 Thus we can rewrite $T^{-1/2}\bar AT^{-1/2}=\sum_{i=1}^n (1-\mu_i)\phi^{(i)} \phi^{(i)'}$.
Let $M= \sum_{i=1}^k (1-\mu_i)\phi^{(i)} \phi^{(i)'}$ and $N=
\sum_{i=k+1}^n (1-\mu_i)\phi^{(i)} \phi^{(i)'}$.
Because $|1-\mu_i|=o(1/\sqrt{\ln n})$ for $k+1 \leq i \leq n$ and the definition of $N$, we have
  \begin{equation*}
  \|N\|=o(1/\sqrt{\ln n}).
  \end{equation*}
   For
a square matrix $B$, we define
$$f(B)=D^{-1/2}T^{1/2}BT^{1/2}D^{-1/2}-B.$$
We shall rewrite $\bar L- L$ as a sum of four matrices. Notice  $\bar L- L=D^{-1/2} A D^{-1/2}- T^{-1/2} \bar A T^{-1/2}$.
 It is easy to verify $\bar L- L=M_1+M_2+M_3+M_4$, where $M_i$  are following.
\begin{align*}
M_1&=T^{-1/2}(A-\bar A)T^{-1/2},\\
M_2 &= f(M_1),\\
M_3&= f(N),\\
M_4&=f(M).
\end{align*}
Here the matrices $M$ and $N$ are defined above. We
will bound $\| M_i\|$ for $1\leq i \leq 4$ separately.


\begin{lemma}\label{l:M1}
If $\delta\gg \ln^4 n$, then asymptotically almost surely
$$\|M_1\| \leq (2+o(1))\frac{1}{\sqrt{\delta}}.$$
\end{lemma}

\begin{proof}
We are going to apply Theorem  \ref{thm:3} to $B=M_1=T^{-1/2}(A-\bar A)T^{-1/2}$.
Note  $$|b_{ij}|\leq (t_it_j)^{-1/2}\leq 1/\delta,$$
and
$$\Var(b_{ij})=\Var( (t_it_j)^{-1/2} (a_{ij}-p_{ij}))=\frac{p_{ij}(1-p_{ij})}{t_it_j}
\leq \frac{p_{ij}}{t_it_j}.$$
Let $K=1/\delta$ and $\sigma_{ij}^2=  \frac{p_{ij}}{t_it_j}$.
We have
$$\Delta(B)=\max_{1\leq i \leq n}\sum_{j=1}^n   \frac{p_{ij}}{t_it_j}
\leq \max_{1\leq i \leq n} \sum_{j=1}^n  \frac{p_{ij}}{t_i\delta}
=\frac{1}{\delta}.$$
By  Theorem  \ref{thm:3}, asymptotically almost surely
$$\|B\|\leq \frac{2}{\sqrt{\delta}} + C \delta^{-3/4} \ln n.$$
When $\delta\gg \ln^4 n$,  we have $C\delta^{-3/4} \ln n=o(\frac{2}{\sqrt{\delta}})$.
Thus, we get $\|M_1\|\leq \frac{2+o(1)}{\sqrt{\delta}}$ asymptotically almost surely and the proof of the lemma is finished.   
\end{proof}


We have the following lemma on the function $f$.

\begin{lemma}\label{l:lm8}
If $\|B\|=o(1/\sqrt{\ln n})$, then asymptotically almost surely $\| f(B)\|=o(1/\sqrt{\delta})$.
\end{lemma}

Before we prove Lemma \ref{l:lm8}, we give two corollaries.

\begin{corollary} \label{l:M2}
If $\delta\gg \ln^4 n$, then
we have $\| M_2 \|=o(1/\sqrt{\delta})$ asymptotically almost surely.
\end{corollary}

\begin{proof}
Recall $M_2=f(M_1)$. By Lemma \ref{l:M1}, asymptotically almost surely we have
$$\|M_1\|\leq \frac{2+o(1)}{\sqrt{\delta}}=o(1/\sqrt{\ln n}).$$
By Lemma \ref{l:lm8}, we have this  Corollary.
\end{proof}


\begin{corollary} \label{l:M3}
If $\delta\gg \ln^4 n$, then asymptotically almost surely
we have  $\| M_3 \|=o(1/\sqrt{\delta}).$
\end{corollary}

\begin{proof}
 Recall $M_3=f(N)$. By the definition of $N$, we have
$\|N\|=o(1/\sqrt{\ln n}) $. Lemma \ref{l:lm8} gives us the Corollary.   
\end{proof}




To prove Lemma \ref{l:lm8}, we need the following well-known Chernoff inequality.
\begin{theorem}{\cite{chernoff}}
\label{chernoff}
 Let $X_1,\ldots,X_n$ be independent random variables with
$$\Pr(X_i=1)=p_i, \qquad \Pr(X_i=0)=1-p_i.$$
We consider the sum $X=\sum_{i=1}^n X_i$,
with expectation $\E(X)=\sum_{i=1}^n p_i$. Then we have
\begin{align*}
\mbox{(Lower tail)~~~~~~~~~~~~~~~~~}
\qquad \qquad  \Pr(X \leq \E(X)-\lambda)&\leq e^{-\lambda^2/2\E(X)},\\
\mbox{(Upper tail)~~~~~~~~~~~~~~~~~}
\qquad \qquad
\Pr(X \geq \E(X)+\lambda)&\leq e^{-\frac{\lambda^2}{2(\E(X) + \lambda/3)}}.
\end{align*}
\end{theorem}

We can use the lemma above to prove the degree of each vertex concentrates around its expectation.

\begin{lemma}\label{l:degree}
Assume $t_i \geq \ln n$ for $1\leq i \leq n$. Then with probability
at least $1-o(1)$, for all $1 \leq i \leq n$ we have
$$
|d_i-t_i| \leq  3 \sqrt{t_i \ln n}.
$$
\end{lemma}
\begin{proof}
Recall $X_{ij}$ is the random indicator variable for $\{i,j\}$ being an edge. Note $d_i=\sum_{j=1}^n X_{ij}$ and $\E(d_i)=\sum_{j=1}^n p_{ij}=t_i$.
Applying the lower tail of Chernoff's inequality with $\lambda=3\sqrt{t_i\ln n}$,
we have
$$\Pr \left (d_i-t_i\leq - \lambda \right ) \leq e^{-\lambda^2/2t_i}=\frac{1}{n^{9/2}}.$$

Applying the upper tail of Chernoff's inequality with $\lambda=3\sqrt{t_i\ln n}$,
we have
$$\Pr \left(d_i-t_i \geq  \lambda \right )
\leq e^{-\frac{\lambda^2}{2(t_i +
 \lambda/3)}}
\leq\frac{1}{n^{27/8}}.$$
The union bound gives the lemma.
  \end{proof}


%By  Lemma \ref{l:degree}, we can write $d_i=(1+o(1))t_i$  for $1 \leq i \leq n$.




\begin{lemma} \label{l:lm7}
When $\delta \gg \ln n$,  asymptotically almost surely we have
$$
  \|D^{-1/2}T^{1/2}-I \| =O\left(\sqrt{\frac{\ln n}{ \delta}}
\right) \hspace{0.2cm}  \mbox{and} \hspace{0.2cm}
\|T^{1/2}D^{-1/2}\|=1+o(1).$$
\end{lemma}
\begin{proof}
We note that $D^{-1/2}T^{1/2}-I $ is diagonal and
the $(i,i)$-th entry is
$\sqrt{t_i/d_i}-1$.  By Lemma \ref{l:degree}, with high probability we have  $|d_i-t_i| \leq 3\sqrt{t_i \ln n}$. We have
\begin{align*}
\left|
\frac{\sqrt{t_i}}{\sqrt{d_i}}-1\right|&=\left|\frac{t_i-d_i}{\sqrt{d_i}(\sqrt{t_i}+\sqrt{d_i})}\right| \\
                                      & \leq \left(\frac{3}{2}+o(1)\right) \sqrt{\frac{\ln n}{t_i}}   \\
                                      & = O\left( \sqrt{\frac{\ln n}{\delta}}\right).
 \end{align*}
The first part of this lemma is proved while the second part follows from the triangle inequality.
The proof of the lemma is finished. 
\end{proof}



We are ready to prove  Lemma \ref{l:lm8}.

\begin{proof}[Proof of Lemma \ref{l:lm8}]
 Recall that $f(B)=D^{-1/2}T^{1/2}BT^{1/2}D^{-1/2}-B$.  We have
\begin{align*}
f(B)&=D^{-1/2}T^{1/2}BT^{1/2}D^{-1/2}-B\\
    &=D^{-1/2}T^{1/2}BT^{1/2}D^{-1/2}-BT^{1/2}D^{-1/2}+BT^{1/2}D^{-1/2}-B\\
    &=(D^{-1/2}T^{1/2}-I)BT^{1/2}D^{-1/2}+B(T^{1/2}D^{-1/2}-I).
\end{align*}
Recall Lemma \ref{l:lm7}. By the triangle inequality, asymptotically almost surely we have
\begin{align*}
\|f(B)\| &\leq  \|D^{-1/2}T^{1/2}-I\| \|B\| \|T^{1/2}D^{-1/2}\|+\|B\|\|(T^{1/2}D^{-1/2}-I)\|\\
         & \leq O\left(\sqrt{\frac{\ln n}{\delta}}\right)\|B\|(1+o(1))+\|B\| O\left(\sqrt{\frac{\ln n}{\delta}}\right)\\
         &=o\left( \frac{1}{\sqrt{\delta}}\right).
\end{align*}
We use the assumption $\|B\|=o(1/\sqrt{\ln n})$ in the last step and
we completed the proof of the lemma.
\end{proof}


\section{Proof of Theorem \ref{thm:2}}
It remains to estimate $\|M_4\|$. Recall $M_4=f(M)$ and
$M=\sum_{i=1}^k (1-\mu_i) \phi^{(i)} \phi^{(i)'}$.

For $1 \leq i \leq n$, write $\phi^{(i)}$ as a column vector
$(\phi^{(i)}_1,\phi^{(i)}_2,\cdots,\phi^{(i)}_n)'$.  Let $\|\phi^{(i)}\|_\infty$
be the maximum over $\{|\phi^{(i)}_1|,|\phi^{(i)}_2|,\cdots,|\phi^{(i)}_n|\}$.
We have the following lemma.
\begin{lemma} \label{l:eigen}
For each $1 \leq i \leq n$, we have
$$
|1-\mu_i| \cdot \|\phi^{(i)}\|_\infty \leq \frac{1}{\sqrt{\delta}}.
$$
\end{lemma}
\begin{proof}
Assume $ \|\phi^{(i)}\|_\infty=|\phi^{(i)}_j|$ for some index $j$. Note that
$\phi^{(i)}$ is a unit vector and  satisfies $T^{-1/2}\bar AT^{-1/2}
\phi^{(i)}=(1-\mu_i) \phi^{(i)}$. In particular, $(T^{-1/2} \bar AT^{-1/2}
\phi^{(i)})_j=(1-\mu_i) \phi^{(i)}_j$ holds. We have
\begin{align*}
|1-\mu_i| \cdot \|\phi^{(i)}\|_\infty  &= |1-\mu_i| |\phi^{(i)}_j|\\
&=|(T^{-1/2} \bar AT^{-1/2} \phi^{(i)})_j|\\
& \leq \sum_{l=1}^n \frac{p_{jl} |\phi^{(i)}_l| }{\sqrt{t_jt_l}} \\
                             &\leq  \left(\sum_{l=1}^n (\phi^{(i)}_l)^2\right)^{1/2} \left(\sum_{l=1}^n \frac{p_{jl}^2}{t_jt_l}\right)^{1/2} \hfill \textrm{(the Cauchy--Schwarz inequality)} \\
                             & \leq \frac{1}{\sqrt{\delta}}
 \left(\sum_{l=1}^n \frac{p_{jl}}{t_j}\right)^{1/2}\\
                             &= \frac{1}{\sqrt{\delta}}.
\end{align*}
The lemma is proved. 
\end{proof}

\begin{lemma} \label{l:variance}
Assume $\delta \gg \ln n$.
For $1 \leq i \leq n$, consider a random variable $X_i:=\frac{(d_i-t_i)^2}{t_i}$.
We have $\E(X_i)\leq 1$ and
$\Var(X_i) \leq 2+o(1)$ for $1 \leq i \leq n$; we also have $\Cov(X_i,X_j)=\frac{p_{ij}(1-p_{ij})(1-2p_{ij})}{t_it_j}$ for $1 \leq i \not = j \leq n$.
\end{lemma}

\begin{proof}
For $1 \leq i< j \leq n$, recall that $X_{ij}$ is the
random indicator  variable for $\{i,j\}$ being an edge.  We define
$Y_{ij}=X_{ij}-p_{ij}$.  Thus we have $d_i-t_i=\sum_{j=1}^n Y_{ij}$.
Note that $\E(Y_{ij})=0$ and $\Var(Y_{ij})=p_{ij}(1-p_{ij})$. We get
$\E(X_i)=\frac{1}{t_i}\sum_{j=1}^{n} p_{ij}(1-p_{ij})\leq 1$.  We have
$$\E(X_i^2)=\frac{1}{t_i^2} \E\left(\sum_{j_1,j_2,j_3,j_4} Y_{ij_1} Y_{ij_2} Y_{ij_3}Y_{ij_4}\right).$$
Since we have $\E(Y_{ij})=0$, the only non-zero terms  in the expectation $\E(Y_{ij})$ occur
 when an index repeated four times, or   two distinct indices are repeated.  The contribution from the
first case is
$$\frac{1}{t_i^2} \sum_{j=1}^n \E(Y_{ij}^4)=\frac{1}{t_i^2} \sum_{j=1}^n (1-p_{ij})^4 p_{ij}+p_{ij}^4(1-p_{ij}) \leq \frac{1}{t_i^2} \sum_{j=1}^n p_{ij}=\frac{1}{t_i}=o(1)$$
as we assume $\delta \gg \ln n$.  The contribution from the second
case is
$$
\frac{3}{t_i^2} \sum_{j_1 \not = j_2} \E(Y_{ij_1}^2) \E(Y_{ij_2}^2)=\frac{3}{t_i^2} \sum_{j_1\not =j_2} p_{ij_1}p_{ij_2}(1-p_{ij_1})(1-p_{ij_2}).
$$
 Thus
$$
\E(X_i^2)=o(1)+\frac{3}{t_i^2} \sum_{j_1 \not =j_2} p_{ij_1}p_{ij_2}(1-p_{ij_1})(1-p_{ij_2}).
$$
We have
\begin{align*}
\left(\E(X_i)\right)^2&=\frac{1}{t_i^2}\sum_{j=1}^n p_{ij}^2(1-p_{ij})^2+\frac{1}{t_i^2}\sum_{j_1 \not =j_2} p_{ij_1}p_{ij_2}(1-p_{ij_1})(1-p_{ij_2})\\
          &=o(1)+ \frac{1}{t_i^2}\sum_{j_1 \not =j_2} p_{ij_1}p_{ij_2}(1-p_{ij_1})(1-p_{ij_2}).
\end{align*}
Therefore we get
\begin{align*}
\Var(X_i)&=\E(X_i^2)-\E(X_i)^2\\
         &=\frac{2}{t_i^2} \sum_{j_1 \not =j_2} \left(p_{ij_1}p_{ij_2}(1-p_{ij_1})(1-p_{ij_2})\right)+o(1) \\
         &\leq  \frac{2}{t_i^2} \sum_{j_1 \not =j_2} \left(p_{ij_1}p_{ij_2}\right)+o(1)\\
         & \leq 2+o(1).
\end{align*}
The covariance $\Cov(X_i,X_j)$ can be computed similarly. Here we omit
the details.
 \end{proof}



\begin{lemma} \label{l:comb}
For any non-negative numbers $a_1, a_2,\ldots a_n$,
let $ X=\sum_{i=1}^n a_i \frac{(d_i-t_i)^2}{t_i}$.  Set $a=\max_{1\leq i\leq n}\{a_i\}$.
Then  we have
$$\Pr\left(X \geq \sum_{i=1}^n a_i + \eta \sqrt{a\sum_{i=1}^n a_i} \ \right)\leq \frac{2+o(1)}
{\eta^2}.$$
\end{lemma}
\begin{proof}
% We have $X=\sum_{i=1}^n a_i X_i$, where
%$X_i=\frac{(d_i-t_i)^2}{t_i}$.
We shall use the second moment method
to show that $X$ concentrates around its expectation. By Lemma \ref{l:variance},
we have $\E(X_i)\leq 1$. Thus $\E(X)\leq \sum_{i=1}^n a_i$.
For the  variance, by Lemma \ref{l:variance} again, we obtain
\begin{align*}
\Var(X) &=  \sum_{i=1}^n a_i^2\Var(X_i)+\sum_{i \not= j}
a_ia_j\Cov(X_i,X_j)\\
& \leq  \sum_{i=1}^n a_i^2 (2+o(1))+  \sum_{i=1}^n \sum_{j=1}^n \frac{a_ia_j p_{ij}(1-p_{ij})(1-2p_{ij})}{t_it_j}\\
        & \leq    (2+o(1)) a \sum_{i=1}^n a_i+ \frac{a}{\delta}\sum_{i=1}^n a_i\sum_{j=1}^n \frac{  p_{ij}}{t_i}\\
 &= (2+o(1))a \sum_{i=1}^n a_i.
\end{align*}
Applying Chebyshev's inequality, we have
\begin{align*}
 \Pr\left(X \geq \sum_{i=1}^n a_i + \eta \sqrt{a\sum_{i=1}^n a_i} \hspace{0.2cm}\right)
&\leq \Pr\left(X-\E(X)\geq \eta \sqrt{a\sum_{i=1}^n a_i}\hspace{0.2cm} \right)\\
&\leq \frac{\Var(X)}{\eta^2 a\sum_{i=1}^n a_i}\\
&\leq \frac{2+o(1)}
{\eta^2}.
\end{align*}
\end{proof}



We are ready to prove an upper bound on $\|M_4\|$.
\begin{lemma}\label{l:M4} If $\delta\gg \{k, \ln^4 n\}$, then asymptotically almost surely
we have
$$\|M_4 \|\leq  (1+o(1))) \frac{\sqrt{\mathstrut \sum_{\lambda\in \Lambda} \mathstrut (1-\lambda)^2}}{\sqrt{\delta}}.$$
\end{lemma}

\begin{proof}
 Recall  that $\{\phi^{(1)}, \phi^{(2)}, \ldots, \phi^{(k)}\}$ is a set of orthogonal unit vectors such that
\[T^{-1/2} \bar A T^{-1/2} \phi^{(i)}=(1-\mu_i) \phi^{(i)}\]
 for each $1 \leq i \leq k$.
Let $\Phi:=(\phi^{(1)}, \ldots,\phi^{(k)})$ be an $n\times k$  matrix whose columns are the vectors $\phi^{(i)}$
and $Q$ be a diagonal $k\times k$ matrix such that $Q_{ii}=1-\mu_i$.
We have $M=\sum_{i=1}^k (1-\mu_i) \phi^{(i)} \phi^{(i)'}=\Phi Q\Phi'$. Thus,
\begin{align*}
M_4& =D^{-1/2}T^{1/2} M T^{1/2} D^{-1/2}-M\\
    &= D^{-1/2}T^{1/2} M T^{1/2} D^{-1/2}-M T^{1/2} D^{-1/2}+M T^{1/2} D^{-1/2} -M \\
    &=(D^{-1/2}T^{1/2} -I) M T^{1/2} D^{-1/2} + M ( T^{1/2}D^{-1/2} - I)\\
&= (D^{-1/2}T^{1/2} -I)\Phi Q \Phi' T^{1/2} D^{-1/2} + \Phi Q \Phi' (T^{1/2} D^{-1/2} - I).
%    &=(D^{-1/2}T^{1/2} -I) \sum_{i=1}^k (1-\mu_i)\phi^{(i)} \phi^{(i)'}  T^{1/2} D^{-1/2} + \sum_{i=1}^k (1-\mu_i)\phi^{(i)} \phi^{(i)'} (T^{1/2} D^{-1/2} - I)
%    &=\sum_{i=1}^k (1-\mu_i)(D^{1-/2}T^{1/2}-I) \phi^{(i)} \phi^{(i)'}T^{1/2}D^{1/2}+\sum_{i=1}^k (1-\mu_i) \phi^{(i)} \phi^{(i)'}(T^{1/2}D^{-1/2}-I).
\end{align*}

Let $U=(D^{-1/2}T^{1/2} -I)\Phi Q$.  By the definition of  $\Phi$,
we have $\|\Phi\|=1$.  By Lemma \ref{l:lm7} and the triangle inequality,
we get
\begin{align*}
  \|M_4\| &= \|U \Phi' T^{1/2} D^{-1/2} + \Phi U'\|\\
&\leq  \|U\| \|\Phi'\| \|T^{1/2} D^{-1/2}\| + \|\Phi\| \| U'\|\\
&=(2+o(1)) \|U\|.
\end{align*}

By the definition of the norm of a non-square matrix, we have
\begin{align*}
  \|U\| &= \sqrt{\|U U'\|} \\
&\leq \sqrt{\tr(UU')}\\
&= \sqrt{\tr\left((D^{-1/2}T^{1/2}-I)\Phi Q Q \Phi' (T^{1/2}D^{-1/2}-I)\right)}\\
&= \sqrt{\sum_{j=1}^n \sum_{i=1}^k (1-\mu_i)^2\left(\phi^{(i)}_j\right )^2
\left( \frac{\sqrt{t_j}}{\sqrt{d_j}} -1 \right)^2}.
\end{align*}

Let $a_j:=\sum_{i=1}^k (1-\mu_i)^2\left(\phi^{(i)}_j\right )^2 $.
We have the following estimate on the norm of $U$,
\begin{align*}
\|U\|^2&\leq \sum_{j=1}^n a_j \left( \frac{\sqrt{t_j}}{\sqrt{d_j}} -1 \right)^2\\
&=  \sum_{j=1}^n a_j \frac{(t_j-d_j)^2}{d_j(\sqrt{t_j}+ \sqrt{d_j})^2}\\
&= (1+o(1))  \sum_{j=1}^n a_j \frac{(t_j-d_j)^2}{4t_j^2}\\
&\leq \frac{1+o(1)}{4\delta}  \sum_{j=1}^n a_j \frac{(t_j-d_j)^2}{t_j}.
\end{align*}


 Note that
\begin{align*}
\sum_{j=1}^n a_j &= \sum_{j=1}^n
\sum_{i=1}^k (1-\mu_i)^2\left(\phi^{(i)}_j\right )^2  \\
&=  \sum_{i=1}^k (1-\mu_i)^2\sum_{j=1}^n\left(\phi^{(i)}_j\right )^2  \\
&=\sum_{i=1}^k (1-\mu_i)^2.
\end{align*}
By Lemma \ref{l:eigen}, we have
$$|1-\mu_i| \cdot \|\phi^{(i)}\|_\infty \leq \frac{1}{\sqrt{\delta}}.$$
Hence, for $1\leq j\leq n$, we get
$$a_j=
\sum_{i=1}^k (1-\mu_i)^2\left(\phi^{(i)}_j\right )^2  \leq
\frac{k}{\delta}.$$
If we let $a=\max_{1\leq j\leq n}\{a_j\}$, then we have $ a \leq  \frac{k}{\delta}$.

Choose $\eta:=\sqrt[3]{\delta}/\sqrt[3]{k}$; we have $\eta\to \infty$ as
$n$ approaches the infinity.
Applying Lemma \ref{l:comb},
with probability $1-o(1)$, we have
\begin{align*}
\sum_{j=1}^n a_j \frac{(t_j-d_j)^2}{t_j}
&\leq \sum_{j=1}^n a_j + \eta \sqrt{a \sum_{j=1}^n a_j} \\
&\leq \sum_{i=1}^k (1-\mu_i)^2 + \frac{\sqrt[3]{\delta}}{\sqrt[3]{k}}
\sqrt{\frac{k}{\delta} \sum_{i=1}^k (1-\mu_i)^2}\\
&= \left(\sqrt{\sum_{i=1}^k (1-\mu_i)^2}+o(1)\right)^2.
\end{align*}
Therefore, we get the following upper bounds on $\|U\|$ and $\|M_4\|$;
$$\|U\|\leq (1+o(1)) \frac{\sqrt{\sum_{i=1}^k (1-\mu_i)^2}}{2\sqrt{\delta}},$$
and
$$\|M_4\| \leq (1+o(1)) \frac{\sqrt{\sum_{i=1}^k (1-\mu_i)^2}}{\sqrt{\delta}}=(1+o(1))) \frac{\sqrt{\mathstrut \sum_{\lambda\in \Lambda} \mathstrut (1-\lambda)^2}}{\sqrt{\delta}}.$$
We proved the lemma. 
\end{proof}


\begin{proof}[Proof of Theorem \ref{thm:2}]
Recall $\bar L- L=M_1+M_2+M_3+M_4$. By the triangle inequality, we have $\| \bar L- L\| \leq
\|M_1\|+\|M_2\|+\|M_3\|+\|M_4\|$.
Combining  Lemma \ref{l:M1}, Corollary \ref{l:M2}, Corollary \ref{l:M3},
and Lemma \ref{l:M4}, we get
\begin{align*}
\|\bar L- L\|&\leq \|M_1\|+\|M_2\|+\|M_3\|+\|M_4\| \\
  &\leq  (2+o(1))\frac{1}{\sqrt{\delta}}+ o\left( \frac{1}{\sqrt{\delta}}\right)+o\left( \frac{1}{\sqrt{\delta}}\right)+  (1+o(1)) \frac{\sqrt{\sum_{i=1}^k (1-\mu_i)^2}}{\sqrt{\delta}}\\
 &=  \left(2+\sqrt{\sum_{i=1}^k (1-\mu_i)^2} +o(1)\right)\frac{1}{\sqrt{\delta}}.
\end{align*}
Note  $\|\bar L-L\|=\|L-\bar L\|$. Finally we apply  Weyl's inequality
\cite{fra}. The proof of Theorem \ref{thm:2} is finished.
\end{proof}




\begin{thebibliography}{99}
\bibitem{akv}
N.~Alon, M.~Krivelevich, and V.~H.~Vu,
 Concentration of eigenvalues of random matrices,
{\em Israel Math.~J.}, {\bf 131} (2002),
259--267.

\bibitem{chernoff}
H.~Chernoff, 
A note on an inequality involving the normal distribution,
{\it Ann.~Probab.}, {\bf 9} (1981),
533--535.



\bibitem{fan4} F.~Chung, {\it Spectral graph theory}, AMS
publications, 1997.

\bibitem{flv1} F.~Chung, L.~Lu, and V.~H.~Vu, Eigenvalues of random power
  law graphs, {\it Ann.~Comb.}, {\bf 7} (2003),  21--33.
\bibitem{flv2} F.~Chung, L.~Lu, and V.~H.~Vu, Spectra of random graphs
  with given expected degrees, {\it Proc.~Natl.~Acad.~Sci.~USA}, {\bf 100}(11) (2003), 6313--6318.
\bibitem{fan7} F.~Chung and M.~Radcliffe, On the spectra of general
  random graphs, {\it Electron.~J.~Combin.}, {\bf 18}(1)  (2011), P215.

\bibitem{og} A.~Coja-Oghlan, On the Laplacian eigenvalues of $G(n,p)$,
  {\it Combin.~Probab.~Comput.}, {\bf 16}(6) (2007),
  923--946.
\bibitem{o} A.~Coja-Oghlan and A.~Lanka, The spectral gap of random
  graphs with given expected degrees, {\it Electron.~J.~Combin.}, {\bf 16} (2009),  R138.
\bibitem{cv}    D.~M.~Cvetkovi\'c, M.~Doob, and H.~Sachs, {\it Spectra of Graphs,
Theory and Applications}, Academic Press, 1980.
\bibitem{dj} X.~Ding and T.~Jiang, Spectral distributions of adjacency
  and Laplacian matrices of random graphs, {\it Ann.~Appl.~Probab.}, {\bf 20}(6) (2010), 2086--2117.



\bibitem{fo}U.~Feige and E.~Ofek, Spectral techniques applied to
  sparse random graphs, {\it Random Structures  Algorithms}, {\bf
    27}(2) (2005), 251--275.

\bibitem{fra} J.~N.~Franklin, Matrix Theory, Prentice--Hall, 1968.
\bibitem{fks} J.~Friedman, J.~Kahn, and E.~Szemer\'edi, On the second eigenvalue in random regular graphs,
in Proc. 21st ACM Symposium on Theory of Computing, Association for
Computing Machinery, New York, 1989, 587--598.

\bibitem{friedman} J.~Friedman,
On the second eigenvalue and random walks in random $d$-regular
graphs,
 {\it Combinatorica},
{\bf 11}(4) (1991), 331--362.

\bibitem{friedman2} J.~Friedman, {\em
A Proof of Alon's Second Eigenvalue Conjecture and Related Problem},
Memoirs of the American Mathematical Society 2008, 100 pp.

\bibitem{fk} Z.~F\"uredi and J.~Koml\'os. The eigenvalues of random
symmetric matrices,{\it Combinatorica,}  {\bf 1}(3) 1981, 233--241.



%\bibitem{ja} S.~Janson, The first
 % eigenvalue of random graphs, {\it Combinatorics, Probability and
  %  Computing,} {\bf 14} (5-6) (2005), 815-828.


\bibitem{ks} M.~Krivelevich and B.~Sudakov, The largest eigenvalue of
  sparse random graphs, {\it Combin.~Probab.~Comput.}, {\bf 12} (2003), 61--72.

%\bibitem{rwalk} L.~Lu and X.~Peng, High-Ordered Random Walks and
%  Generalized Laplacians on Hypergraphs, in A.~Frieze, P.~Horn,
%  P.~Pralat (Eds.): {\em Algorithms and Models for the Web Graph - 8th
%    International Workshop, (WAW 2011) Proceedings}. Lecture Notes in
%  Computer Science {\bf 6732} Springer 2011, 14-25.

\bibitem{oli} R.~Oliveira, Concentration of the adjacency matrix and of the Laplacian
in random graphs with independent edges, [math.CO].
\bibitem{tropp} J.~Tropp, User-friendly tail bounds for sums of random matrices, {\it Found.~Comput.~Math.}, {\bf 12}(4) 2012, 389--434.

\bibitem{vu} V.~H.~Vu, Spectral norm of random matrices,
{\it Combinatorica}, {\bf 27} (6) (2007), 721--736.

\bibitem{wigner} E.~P.~Wigner,  On the  distribution of the roots of certain symmetric matrices, {\it Ann.~Math.},
{\bf 67} (1958), 325--327.


\end{thebibliography}


\end{document}
