In this twopart talk, we discuss several combinatorics problems rooted in the study of random walks. In the first half, we discuss problems in extremal spectral graph theory pertaining to random walk parameters. Focusing first on undirected graphs, we find the minimum spectral gap of the normalized Laplacian matrix over all simple, connected nvertex graphs, settling a conjecture of Aldous and Fill. Turning attention to directed graphs, we then consider the principal ratio, a measure of digraph irregularity based on the maximum to minimum values of vertices in the stationary distribution. We also discuss the directed analog of the normalized Laplacian matrix, and prove a lower bound on its spectral gap.
In the second half, we propose a Laplacian based approach for clustering hypergraphstructured data. Our proposed method is rooted in recent work, which has advocated utilizing edgedependent vertex weights to define nonreversible hypergraph random walks. Based on these, we employ tools developed in the first half of the talk to construct hypergraph Laplacians and design clustering algorithms that utilize them as inputs. Testing on real data, we compare the performance of these clustering algorithms experimentally against a variety of existing hypergraph clustering methods.
Random walks on graphs and hypergraphs: eigenvalues and clustering
Sinan Aksoy

Online. Contact Prof. Soumik Pal for details.