Ramanujan graphs, quaternion algebras, and supersingular elliptic curves

Expanders are sparse graphs that are highly connected. These two properties together make them prominent in both pure and applied mathematics, as well as computer science. Explicit constructions of these graphs are required for their use in many applications. But, although existence of expanders is rather easy to be proved, explicit constructions turn out to be surprisingly non-trivial. Ramanujan graphs are the optimal expanders, in the sense that they achieve asymptotically the largest expansion. In this thesis, we present an explicit construction of a family of constant degree Ramanujan graphs discovered by Pizer. These graphs are defined via the Brandt matrix of an Eichler order in quaternion algebras over $\mathbb{Q}$. We prove how these graphs attain the Ramanujan bound using the Ramanujan-Petersson Conjecture proved by Deligne. Furthermore, using the Deuring correspondence, we prove that the supersingular isogeny graphs is a subclass of these graphs and thus they are also...Show moreExpanders are sparse graphs that are highly connected. These two properties together make them prominent in both pure and applied mathematics, as well as computer science. Explicit constructions of these graphs are required for their use in many applications. But, although existence of expanders is rather easy to be proved, explicit constructions turn out to be surprisingly non-trivial. Ramanujan graphs are the optimal expanders, in the sense that they achieve asymptotically the largest expansion. In this thesis, we present an explicit construction of a family of constant degree Ramanujan graphs discovered by Pizer. These graphs are defined via the Brandt matrix of an Eichler order in quaternion algebras over $\mathbb{Q}$. We prove how these graphs attain the Ramanujan bound using the Ramanujan-Petersson Conjecture proved by Deligne. Furthermore, using the Deuring correspondence, we prove that the supersingular isogeny graphs is a subclass of these graphs and thus they are also Ramanujan.Show less

Leiden University Student Repository

Documents

In Collections

Ramanujan graphs, quaternion algebras, and supersingular elliptic curves