Building Ramanujan Graphs

This lecture discusses the challenges of using the probabilistic method to construct Ramanujan graphs and proposes a solution involving polynomials. The instructor explains the concept of expander graphs and their role in solving NP-hard problems. The lecture covers topics such as belief negotiation, continuous and discrete distances, and the properties of Ramanujan graphs. It also delves into the interplay between eigenvalues and eigenvectors of matrices, emphasizing the importance of tracking all eigenvalues. The presentation concludes with a detailed analysis of interlacing properties and characteristic polynomials, showcasing their significance in graph theory and linear algebra.