Noisy random graphs and their laplacians (Q941350)

This paper deals with the spectra of weighted graphs. Define a Wigner-noise matrix to be an \(n\times n\) matrix \(W\) whose entries \(w_{ij}\) are uniformly bounded random variables with expectations zero and variances bounded by some \({\sigma^2}\), informally, a small noisy perturbation matrix. The eigenvalues of such \(W\) are known to be \` small\'\, with probability tending to 1, in a precise sense, by a result of Füredi and Komlós. The author then considers the effect of replacing a weighted adjacency matrix \(B\) of some \(n\)-vertex graph \(G\) by \(A=W+B\) where \(W\) is a Wigner-noise matrix for certain particular choices of weighted graph \(G\) with \(n\) vertices and weighted adjacency matrix \(B\). At first, \(B\) is a Kronecker-sum of \(n_{i}\times n_{i}\) matrices \(B_{i}\) (where \(\sum_{i=1}^{k}n_{i}=n\)) and each \(B_{i}\) has all off-diagonal entries equal to \(\mu_{i}\) and all diagonal entries equal to \(\nu_{i}\). (Thus \(G\) has \(k\) components, each pair of vertices connected with an edge of the same weight). Somewhat more generally, \(B\) has a so-called pattern matrix: this means that \(V(G)=V_{1}\cup V_{2}\cup \ldots \cup V_{k}\) where \(| V_{i}|=n_{i}\) and all edge weights between a vertex in \(V_{i}\) and one in \(V_{j}\) have weight \(p_{ij}\): here \(P=(p_{ij})\) is the \(k\times k\) pattern matrix. \(B\) is then called a blown-up matrix. For both cases, the author has proven in earlier papers that there are \(k\) \` protruding\'\, eigenvalues of order \(\Theta(n)\) of \(B\) with the others being smaller, provided the so-called growth condition holds, namely that each \(n_{i}\geq Cn\). Section 2 of the paper uses linear algebra methods to give an alternative proof that, under the growth rate condition, all non-zero eigenvalues of the \(n\times n\) blown-up matrix \(B\) are order \(n\) in absolute value. This then leads to the fact that the protruding eigenvalues of \(A\) can be found and the block structure of \(B\) can be read off from the eigenvectors of \(A\). The author also considers weighted Laplacians \(L^{\prime}(A)\), (recall the Laplacian is \(D-A\) where \(D\) is a diagonal matrix with diagonal entries the degrees of the vertices: then \(L^{\prime}(A)=I_{n}-D(A)^{-1/2}AD(A)^{-1/2}\) (if no vertex is isolated). She shows that, under the growth rate condition, there are \(k\) eigenvalues of \(L^{\prime}(B)\) which are not equal to 1 and they are located in the union of intervals \([0,1-\delta]\cup [1+\delta,2]\) for a constant \(\delta\in (0,1)\): the proof is again linear algebra. Again this leads to the statement of a similar result for \(L^{\prime}(A)\), which it is said will be proved in a later paper. Again eigenvectors of \(A\) will reveal the block structure in \(B\). The author closes by discussing links with the Szemerédi Regularity Lemma briefly.