Pseudo Randomness in Graphs

This lecture delves into the concept of pseudo randomness in graphs, focusing on the characterization using eigenvalues of the adjacency matrix for D-regular graphs. The discussion extends to the construction of graphs with non-trivial eigenvalues lying within a specific range, known as Ramanujan graphs. The instructor explores the probabilistic approach using the Laplacian matrix to achieve pseudo randomness, emphasizing the importance of bunched roots in polynomials. The lecture progresses to the application of the matrix determinant lemma to understand the behavior of characteristic polynomials when adding rank one matrices. The concept of common interlacers in polynomials is introduced, leading to insights on the probabilistic combinatorics tool for analyzing eigenvalues of random matrices.