\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 ij$, 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}