UC San Diego

This thesis concerns the spectral and combinatorial properties of sparse random graphs and hypergraphs. We present three models, including inhomogeneous random graphs, random bipartite biregular graphs, and the hypergraph stochastic block model, emphasizing the limiting spectral distributions, eigenvalue fluctuations, and top eigenvalues and eigenvectors, respectively. We first present a graphon approach to finding the limiting spectral distribution of Wigner-type matrices, building a connection between random matrices and graph limits. For random bipartite biregular graphs, we analyze their cycle structure and compute the global eigenvalue fluctuations. Finally, we study a spectral algorithm for community detection in sparse hypergraph stochastic block models using a new matrix that counts self-avoiding walks on hypergraphs.