Algebraic Constructions of Ramanujan Graphs and Applications to Error Correcting Codes
Author
Polatajko, Daniel Brian
Metadata
Show full item recordCitation
Polatajko, Daniel Brian. 2019. Algebraic Constructions of Ramanujan Graphs and Applications to Error Correcting Codes. Bachelor's thesis, Harvard College.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.Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37364612
Collections
- FAS Theses and Dissertations [6847]
Contact administrator regarding this item (to report mistakes or request changes)