Spectra of Sparse Random Graphs and Some Related Problems

在真实的世界中，节点数量非常多但每个节点的邻居相对较少的网络是大量存在的。这些例子包括，除其他外，万维网和大脑神经元网络。这些真实世界的网络可以有效地建模稀疏随机图，其中顶点对之间的链接在一定的随机规则下添加。这些随机图具有非常复杂的几何形状。理解它们的几何的一种方法是研究图的特征值和特征向量。例如，通过查看特征值和特征向量，可以推断网络的拥塞程度，或者识别网络中存在的不同集群。这个建议的一个重要部分是专门研究这些稀疏随机图的特征值和特征向量，其中很少有人知道到目前为止。这些具有相关本征值和本征向量的随机图也被用作研究电子在无序介质（即含有杂质的介质）中传播的数学模型。本提案中概述的一些问题是出于理解无序介质中电磁波传输的目标。拟议的研究将涉及PI与来自美国和国际大学的许多研究人员之间的积极合作。这个提议包括概率论的三个研究方向，都与稀疏随机图的谱有关。本文的第一部分研究了平均顶点度有界的随机图的不同模型的邻接矩阵的特征值分布。在极限情况下，随着图的大小增长到无穷大，这些特征值分布表现出非常复杂的行为范围。PI将研究各种稀疏随机图模型的特征值分布特性，包括具有给定度分布的随机图和欧几里得格上的稀疏图，主要关注极限特征值分布中的三个关键特征-连续部分的存在，多个原子和支撑中的间隙。一个大的稀疏随机图的邻接矩阵可以被用来作为一个无序介质上的电子跳跃的哈密顿量和其本征值分布的研究是一个初步的步骤，了解是否介质的行为像金属或绝缘体在不同的能量。该建议的第二部分涉及波多野和纳尔逊提出的一个模型，用于研究半导体中磁通线的运动。这可以被认为是一维中著名的安德森模型的非厄米模拟。波多野和纳尔逊观察到与真实的和复杂的本征值相关的本征向量的对比本地化行为。PI建议严格调查这一现象，并试图理解所谓的特征向量的“离域过渡”。最后一部分是稀疏随机图的组合优化问题。这些问题中的每一个都涉及与底层图的谱相连接的组合结构，但它们本身是有趣的。其中之一是了解欧几里德格上最小权完美匹配的行为。这个优化问题的变体在文献中得到了很多关注。总的来说，这个建议包括广泛的问题，其解决方案将包括一套不同的工具和想法的组合，从随机矩阵理论，随机薛定谔算子，图论，统计物理，添加剂组合和概率。

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.