Caltech Logo

LA Probability Forum

Thursday, April 27, 2023
6:00pm to 7:00pm
Add to Cal
Linde Hall 310
Extreme eigenvalues in bipartite Erdos-Renyi graphs
Ioana Dumitriu, Department of Mathematics, UCSan Diego,

The asymptotic (and non-asymptotic) behavior of extreme eigenvalues is a fundamental topic in random matrix theory; such eigenvalues can be used to provide theoretical guarantees for randomized linear algebra on large data sets, with applications in machine learning, signal processing, and data science. The spectra of random bipartite graphs has a basic connection to the set of singular values of random rectangular matrices and can also connect to the spectra of more general graph and hypergraph operators; understanding their spectra is thus of particular interest. Several avenues for studying these extremal eigenvalues / singular values for non-homogeneous Erdos-Renyi graphs have been explored, most importantly through the seminal work of Bandeira, Boedihardjo, and Van Handel (2021). Though very sharp, their bounds do not extend to the near critical regime when sparsity approaches the connectivity threshold; in a new paper with Yizhe Zhu (2022), we provide a non-backtracking operator approach inspired by Benaych-Georges, Bordenave, and Knowles (2019) which, while slightly less sharp, reaches all the way to the connectivity threshold. Notably, the bound is sharp in the homogeneous case up to just above criticality.

For more information, please contact Math Dept by phone at 626-395-4335 or by email at [email protected].