Emil Bertlin: Spectral Graph Theory: Paley and Ramanujan Graphs

Abstract: A fundamental question in spectral graph theory asks how the eigenvalues of a graph reflect its combinatorial properties. Ramanujan graphs are regular graphs whose nontrivial eigenvalues are as small as possible, a spectral condition that makes them well connected but sparse. The Alon–Boppana bound shows that, asymptotically, this property is the best one can hope for among bounded-degree graphs. This thesis approaches Ramanujan graphs from two complementary perspectives. The first studies Paley graphs, an explicit family whose construction draws on finite fields and number theory. Using Cayley graphs, character theory, and the quadratic Gauss sum, we establish their spectrum. Following this, a proof that the Paley graphs satisfy the Ramanujan bound is provided. The second perspective studies the existence of Ramanujan graphs through a nonconstructive proof by Marcus, Spielman, and Srivastava, which establishes the existence of an infinite family of d-regular bipartite Ramanujan graphs for every integer d > 2. Between these viewpoints, expander graphs are explored through Cheeger’s inequality and the Alon–Boppana bound in order to place the Ramanujan property in its natural setting of expander families. The exposition develops the necessary background alongside the main theorems and supplies proofs of many results that the original literature leaves to references