Spectra of Sparse Random Graphs and Some Related Problems

具有大量节点但每个节点的邻居相对较少的网络在现实世界中是丰富的。这些例子包括万维网和大脑神经元网络等。这些现实世界的网络可以通过稀疏随机图有效地建模，其中在一定的随机规则下添加对顶点之间的链接。这些随机图具有非常复杂的几何结构。理解它们几何形状的一种方法是研究图的特征值和特征向量。例如，通过观察特征值和特征向量，可以推断网络的拥塞程度，或者识别网络中存在的不同集群。本文的主要内容是研究稀疏随机图的特征值和特征向量，目前对稀疏随机图的研究还很少。这些具有相关特征值和特征向量的随机图也可用作研究电子在无序介质（即含杂质介质）中的传播的数学模型。本提案中概述的一些问题的动机是为了理解电磁波在无序介质中的传输。拟议的研究将涉及PI与来自美国和国际大学的许多研究人员之间的积极合作。本文提出概率论研究的三个方向，均与稀疏随机图的谱有关。本文第一部分研究了有界平均顶点度随机图的不同模型邻接矩阵的特征值分布。在极限情况下，当图的大小增长到无穷大时，这些特征值分布表现出非常复杂的行为范围。PI将研究各种稀疏随机图模型的特征值分布性质，包括给定度分布的随机图和欧几里得格上的渗透，主要关注极限特征值分布的三个关键特征-连续部分的存在，有限多原子和支撑中的间隙。大型稀疏随机图的邻接矩阵可以作为无序介质上电子跳跃的哈密顿量，研究其特征值分布是理解介质在不同能量下是像金属还是像绝缘体的初步步骤。本提案的第二部分涉及由Hatano和Nelson提出的用于研究半导体磁通量线运动的模型。这可以看作是著名的安德森模型在一维中的非厄米模拟。Hatano和Nelson观察到与实特征值和复特征值相关的特征向量的不同的局部化行为。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.