Spectra of Sparse Random Graphs and Some Related Problems

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

The networks with a very large number of nodes but each node having a relatively few neighbors are abundant in the real world. The examples include, among others, the World Wide Web and the networks of brain neurons. These real-world networks can be effectively modeled by sparse random graphs where the links between the pair of vertices are added under certain stochastic rules. These random graphs have very complex geometry. One way to understand their geometry is to study what are called the eigenvalues and the eigenvectors of the graphs. For example, by looking at the eigenvalues and eigenvectors one can infer how congested the network is, or identify the different clusters present in the network. A significant part of this proposal is devoted to the study of the eigenvalues and eigenvectors of these sparse random graphs of which very little is known so far. These random graphs with the associated eigenvalues and eigenvectors are also used as a mathematical model to study the propagation of electrons in a disordered medium, that is, a medium with impurities. Some of the questions outlined in this proposal are motivated by the goal of understanding the transport of electromagnetic waves in disordered media. The proposed research will involve active collaborations between the PI and a number of researchers from various US and international universities. This proposal consists of three directions of research in probability theory, all related to the spectra of sparse random graphs. The first part of this proposal deals with the study of eigenvalue distributions of the adjacency matrices of different models of random graphs with bounded average vertex degrees. In the limit, as the size of the graphs grows to infinity, these eigenvalue distributions exhibit a remarkably complex range of behaviors. The PI will study properties of the eigenvalue distribution for various sparse random graph models, including random graphs with a given degree distribution and percolations on Euclidean lattices, primarily focusing on three key features in the limiting eigenvalue distributions- existence of continuous part, finitely many atoms and gaps in the support. The adjacency matrix of a large sparse random graph can be used as a Hamiltonian for electron hopping on a disordered medium and the study of its eigenvalue distribution is a preliminary step towards understanding whether the medium behaves like a metal or an insulator at different energies. The second part of this proposal deals with a model which was introduced by Hatano and Nelson to study the motion of magnetic flux lines in semiconductors. This can be thought as a non-Hermitian analogue of the famous Anderson model in one dimension. Hatano and Nelson observed contrasting localization behaviors of the eigenvectors associated with the real and the complex eigenvalues. The PI proposes to investigate this phenomenon rigorously and try to understand so-called 'delocalization transition' of the eigenvectors. The final part of this proposal involves a couple of combinatorial optimization problems on sparse random graphs. Each of these problems deals with a combinatorial structure that is connected to the spectra of the underlying graph, but they are interesting on their own. One of them is to understand the behavior of the minimum weight perfect matching on the Euclidean lattices. The variants of this optimization problem has received a lot of attention in the literature. Overall, this proposal consists of a wide range of problems whose solutions will include a combination of a diverse set of tools and ideas from random matrix theory, random Schrodinger operators, graph theory, statistical physics, additive combinatorics and probability.