Show simple item record

dc.contributor.authorPolatajko, Daniel Brian
dc.date.accessioned2020-08-28T09:32:05Z
dc.date.created2019-05
dc.date.issued2019-08-23
dc.date.submitted2019
dc.identifier.citationPolatajko, Daniel Brian. 2019. Algebraic Constructions of Ramanujan Graphs and Applications to Error Correcting Codes. Bachelor's thesis, Harvard College.
dc.identifier.urihttps://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37364612*
dc.description.abstractThis 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.sponsorshipComputer Science
dc.description.sponsorshipComputer Science
dc.format.mimetypeapplication/pdf
dc.language.isoen
dash.licenseLAA
dc.titleAlgebraic Constructions of Ramanujan Graphs and Applications to Error Correcting Codes
dc.typeThesis or Dissertation
dash.depositing.authorPolatajko, Daniel Brian
dc.date.available2020-08-28T09:32:05Z
thesis.degree.date2019
thesis.degree.grantorHarvard College
thesis.degree.grantorHarvard College
thesis.degree.levelUndergraduate
thesis.degree.levelUndergraduate
thesis.degree.nameAB
thesis.degree.nameAB
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.departmentComputer Science
dash.identifier.vireo
dash.author.emaildanielpolatajko@gmail.com


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record