On the spectra of large sparse graphs with cycles

This paper investigates the asymptotic nature of graph spectra when some edges of a graph are subdivided sufficiently many times. In the special case where all edges of a graph are subdivided, we find the exact limits of the $k$-th largest and $k$-th smallest eigenvalues for any fixed $k$. It is expected that after subdivision, most eigenvalues of the new graph will lie in the interval $[-2,2]$. We examine the eigenvalues of the new graph outside this interval, and we prove s...

Spectral graph theory is a captivating area of graph theory that employs the eigenvalues and eigenvectors of matrices associated with graphs to study them. In this paper, we present a collection of $20$ topics in spectral graph theory, covering a range of open problems and conjectures. Our focus is primarily on the adjacency matrix of graphs, and for each topic, we provide a brief historical overview.

We examine the empirical distribution of the eigenvalues and the eigenvectors of adjacency matrices of sparse regular random graphs. We find that when the degree sequence of the graph slowly increases to infinity with the number of vertices, the empirical spectral distribution converges to the semicircle law. Moreover, we prove concentration estimates on the number of eigenvalues over progressively smaller intervals. We also show that, with high probability, all the eigenvect...

We compute spectra of large stochastic matrices $W$, defined on sparse random graphs, where edges $(i,j)$ of the graph are given positive random weights $W_{ij}>0$ in such a fashion that column sums are normalized to one. We compute spectra of such matrices both in the thermodynamic limit, and for single large instances. The structure of the graphs and the distribution of the non-zero edge weights $W_{ij}$ are largely arbitrary, as long as the mean vertex degree remains finit...

We study some spectral properties of a matrix that is constructed as a combination of a Laplacian and an adjacency matrix of simple graphs. The matrix considered depends on a positive parameter, as such we consider the implications in different regimes of such a parameter, perturbative and beyond. Our main goal is to relate spectral properties to the graph's configuration, or to basic properties of the Laplacian and adjacency matrices. We explain the connections with dynamic ...

Complex networks or graphs are ubiquitous in sciences and engineering: biological networks, brain networks, transportation networks, social networks, and the World Wide Web, to name a few. Spectral graph theory provides a set of useful techniques and models for understanding `patterns of interconnectedness' in a graph. Our prime focus in this paper is on the following question: Is there a unified explanation and description of the fundamental spectral graph methods? There are...

Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than $2g$, where $g$ is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum $\{\eta_i\}$ of the directed edge matrix of the graph to compu...

This review presents an account of the major works done on spectra of adjacency matrices drawn on networks and the basic understanding attained so far. We have divided the review under three sections: (a) extremal eigenvalues, (b) bulk part of the spectrum and (c) degenerate eigenvalues, based on the intrinsic properties of eigenvalues and the phenomena they capture. We have reviewed the works done for spectra of various popular model networks, such as the Erd\H{o}s-R\'enyi r...

We study the spectral properties of certain non-self-adjoint matrices associated with large directed graphs. Asymptotically the eigenvalues converge to certain curves, apart from a finite number that have limits not on these curves.

The spectrum of a network or graph $G=(V,E)$ with adjacency matrix $A$, consists of the eigenvalues of the normalized Laplacian $L= I - D^{-1/2} A D^{-1/2}$. This set of eigenvalues encapsulates many aspects of the structure of the graph, including the extent to which the graph posses community structures at multiple scales. We study the problem of approximating the spectrum $\lambda = (\lambda_1,\dots,\lambda_{|V|})$, $0 \le \lambda_1,\le \dots, \le \lambda_{|V|}\le 2$ of $G...