dc.contributor.author Polatajko, Daniel Brian dc.date.accessioned 2020-08-28T09:32:05Z dc.date.created 2019-05 dc.date.issued 2019-08-23 dc.date.submitted 2019 dc.identifier.citation Polatajko, Daniel Brian. 2019. Algebraic Constructions of Ramanujan Graphs and Applications to Error Correcting Codes. Bachelor's thesis, Harvard College. dc.identifier.uri https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37364612 * dc.description.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. dc.description.sponsorship Computer Science dc.description.sponsorship Computer Science dc.format.mimetype application/pdf dc.language.iso en dash.license LAA dc.title Algebraic Constructions of Ramanujan Graphs and Applications to Error Correcting Codes dc.type Thesis or Dissertation dash.depositing.author Polatajko, Daniel Brian dc.date.available 2020-08-28T09:32:05Z thesis.degree.date 2019 thesis.degree.grantor Harvard College thesis.degree.grantor Harvard College thesis.degree.level Undergraduate thesis.degree.level Undergraduate thesis.degree.name AB thesis.degree.name AB dc.type.material text thesis.degree.department Computer Science thesis.degree.department Computer Science dash.identifier.vireo dash.author.email danielpolatajko@gmail.com
﻿