Loops, Multi-Edges and Collisions in Supersingular Isogeny Graphs

Abstract

Supersingular isogeny graphs are known to have very few loops and multi-edges. We formalize this idea by studying and finding bounds for the number of loops and multi-edges in such graphs. We also find conditions under which the supersingular isogeny graph ${\Lambda }_p(\ell )$ is simple. The methods presented in this paper can be used to study many kinds of collisions in supersingular isogeny graphs. As an application, we introduce the notion of bi-route number for two graphs ${\Lambda }_p({\ell }_1),{\Lambda }_p({\ell }_2)$ and compute bounds for it. We also study the number of edges in common between the graphs ${\Lambda }_p({\ell }_1),{\Lambda }_p({\ell }_2)$.

arXiv comment21 pages