Mathematics Colloquium: Submodular Random Walks

2022-10-27

12:00pm -- CUE 409

Stephen Young

Recently Li & Milenkovic and Yoshida independently developed the idea of a Laplacian for a collection submodular functions over the subset lattice which generalizes existing Laplacians over graphs, directed graphs, and hypergraphs. Along with the Laplacian they both define similar versions of the Cheeger ratio and inequality and provide means of efficiently approximating spectra of the Laplacians. In this presentation we explore extending the work of Li & Milenkovic and Yoshida to define a random walk on the base elements of the subset lattice whose evolution is governed by a collection of submodular functions. Joint work with Sinan Aksoy and Bill Kay.