Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Interlacing Families and Ramanujan Graphs
This lecture covers the concept of interlacing families and 1-sided Ramanujan graphs. The instructor discusses characteristic polynomials and matching polynomials in trees and graphs. The lecture explores the properties of signed adjacency matrices and the probabilistic method for constructing Ramanujan graphs. It also delves into the existence of 1-sided Ramanujan graphs and the proof of their existence. Additionally, the lecture touches upon the unsolved problem of 2-sided Ramanujan graphs. The instructor presents examples and explains the significance of these concepts in graph theory.