Algebraic Constructions of Ramanujan Graphs and Applications to Error Correcting Codes

Abstract

This thesis gives an exposition on explicit constructions of Ramanujan graphs, paying close attention to the first such construction of Lubotzky, Phillips and Sarnak in [16], and dis-cussing some of the interesting combinatorial, algebraic, and number theoretic techniques used to construct such graphs. This construction is particularly noteworthy mathematically because it combines far-reaching and seemingly unrelated topics in mathematics. M.Ram Murty describes Ramanujan graphs as “[fusing] diverse branches of pure mathematics,namely, number theory, representation theory, and algebraic geometry” in a survey paper on the topic [20]. The interest in such constructions is, however, not purely mathematical.Ramanujan graphs are a subset of a class of important graphs known as expanders, which colloquially have the property of being highly connected, but using relatively few edges to establish those connections. These have found myriad applications in many fields of mathematics, computer science, and beyond. We will discuss expansion properties in graphs in general, before demonstrating the optimality of one specific expansion property of Ramanujan graphs, and then move on to a discussion of the usefulness of expander graphs in some familiar topics of computer science. Particularly, we will focus on an application of expander graphs in constructing error correcting codes, and derive some results showing that error correcting codes constructed from Ramanujan graphs have desirable asymptotic behaviour.