Random Matrices and Functional Inequalities on Spaces of Graphs

这个研究项目侧重于概率论的两个基本概念：随机矩阵（随机数据的矩形阵列）和图上的随机游动。随机矩阵自然地出现在计算机科学、统计学和数学物理中的问题中。研究随机矩阵使人们能够开发更好的工具来分析数据，理解复杂量子系统的特性，并估计算法的性能。主要研究者（PI）将考虑各种随机矩阵模型，目的是获得具有极高概率的结果。图（由边连接的点的集合）已被广泛用作通信网络和数据组织的模型。例如，社交网络和万维网可以被有效地建模为随机图。了解图上随机游动的特性有助于评估网络中信息交换的速度。此外，在某些图上的随机游走已被用于采样，即构造复杂对象的典型实例。PI将通过使用泛函分析的工具来研究图上随机游动的性质。该项目为研究生提供研究培训机会。本文的主要研究内容包括两个方面：一类随机方阵的奇异谱和特征值的分析，以及图上的泛函不等式。PI将专注于研究随机方阵的奇异概率，这在数值分析和组合学中很有意义。此外，PI将考虑以前未探索过的模型的随机矩阵谱的极限定律。作为本研究的一部分，开发的工具应该在组合和非渐近随机矩阵理论的其他问题中找到应用。其次，PI将应用函数分析工具来研究各种图上的集中和混合，包括正则图空间和Catalan结构。该项目的这一部分的目标是获得这些图上随机游走的混合和松弛时间的精确估计。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

This research project focuses on two fundamental notions of probability theory: random matrices (rectangular arrays of random data) and random walks on graphs. Random matrices naturally appear in problems within computer science, statistics, and mathematical physics. Studying random matrices enables one to develop better tools to analyze data, to understand properties of complex quantum systems, and to estimate performance of algorithms. The Principal Investigator (PI) will consider various models of random matrices with the goal of obtaining results that hold with very high probability. Graphs (collections of points connected by edges) have been extensively used as models of communication networks and of data organization. For example, social networks and the World Wide Web can be efficiently modeled as random graphs. Understanding characteristics of random walks on graphs helps to evaluate the speed of information exchange in networks. Moreover, random walks on certain graphs have been used for sampling, that is, constructing typical instances of complex objects. The PI will study properties of random walks on graphs by employing tools of functional analysis. The project provides research training opportunities for graduate students. The two main parts of this research are analysis of singular spectrum and eigenvalues of certain models of square random matrices, and functional inequalities on graphs. The PI will focus on studying the singularity probability of random square matrices, which is of interest in numerical analysis and combinatorics. Further, the PI will consider limiting laws for the spectrum of random matrices for previously unexplored models. The tools developed as part of this research should find applications in other problems within combinatorial and non-asymptotic random matrix theory. Secondly, the PI will apply functional analytic tools to study concentration and mixing on various graphs, including spaces of regular graphs, and Catalan structures. The goal of this part of the project is to obtain sharp estimates for mixing and relaxation times for random walks on those graphs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.