Spectra of Sparse Random Graphs and Some Related Problems

稀疏随机图的谱及相关问题

• 批准号: 1406247
• 负责人: Arnab Sen
• 金额: $ 15.3万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1406247&HistoricalAwards=false
• 关键词: Spectra; Sparse; Random; Graphs; Some

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.

在现实世界中，具有非常多的节点但每个节点的邻居相对较少的网络是非常丰富的。这些例子包括万维网和大脑神经元网络。这些现实世界的网络可以有效地用稀疏随机图来建模，其中顶点对之间的链接是按照一定的随机规则添加的。这些随机图具有非常复杂的几何形状。理解它们几何的一种方法是研究被称为图的特征值和特征向量的东西。例如，通过查看特征值和特征向量，可以推断网络的拥塞程度，或者识别网络中存在的不同簇。这项建议的很大一部分致力于研究这些稀疏随机图的特征值和特征向量，到目前为止，对这些稀疏随机图的了解很少。这些带有相关本征值和本征向量的随机图也被用作研究电子在无序介质(即含有杂质的介质)中的传播的数学模型。这项提案中概述的一些问题是为了了解电磁波在无序介质中的传输。这项拟议的研究将涉及国际和平研究所与来自美国和国际大学的一些研究人员的积极合作。这一建议包括概率论的三个研究方向，都与稀疏随机图的谱有关。本文的第一部分研究了具有有界平均顶点度的随机图的不同模型的邻接矩阵的特征值分布。在极限情况下，当图的大小增长到无穷大时，这些特征值分布表现出非常复杂的行为范围。PI将研究各种稀疏随机图模型的特征值分布的性质，包括具有给定度分布的随机图和欧几里得格上的渗流，主要集中在极限特征值分布的三个关键特征--连续部分的存在、有限多的原子和支撑体中的间隙。一个大型稀疏随机图的邻接矩阵可以作为无序介质上电子跳跃的哈密顿量，研究它的本征值分布是了解无序介质在不同能量下的行为是金属还是绝缘体的初步步骤。这个建议的第二部分涉及Hatano和Nelson提出的一个模型，该模型用于研究半导体中磁通线的运动。这可以被认为是著名的安德森模型在一维的非厄米特类比。Hatano和Nelson观察到与实特征值和复特征值相关的特征向量的局部化行为截然不同。PI建议对这一现象进行严格的研究，并试图理解所谓的本征向量的“离域转变”。该方案的最后一部分涉及稀疏随机图上的几个组合优化问题。这些问题中的每一个都涉及与基础图的谱相关联的组合结构，但它们本身就很有趣。其中之一是了解欧几里得格子上的最小重量完美匹配的行为。这种优化问题的变体在文献中受到了很大的关注。总体而言，这一建议包括一系列问题，其解决方案将包括来自随机矩阵理论、随机薛定谔算子、图论、统计物理、加法组合学和概率论的各种工具和思想的组合。