Random Matrices and Functional Inequalities on Spaces of Graphs

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.