Eigenvalues, Matroids and Graphs: Part I

The nontrivial lower bounds of the spectral gap for discrete Laplacian of the basis-exchange graph of a Matroid have algorithmic importance. In the first part of this presentation, we will present some background knowledge such as matroids, basis-exchange graph, and eigenvalue of the Laplacian. In the second part, several new and old lower bounds of the spectral gap for the basis-exchange graphs will presented and applied to algorithmic questions.

Event Topic

Discrete Applied Math Seminar