Loops, Multi-Edges and Collisions in Supersingular Isogeny Graphs

2021/01/21 by Wissam Ghantous, Ghantous, Wissam
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #14H52 #14K02 #Algorithms and Data Compression #DNA and Biological Computing #FOS: Mathematics #Interconnection Networks and Systems #Number Theory (math.NT) #math.NT #msc:14H52 #msc:14K02

paper · pdf · doi:10.48550/arxiv.2101.08761

21 pages

openalex publication_date 2021/01/21 · arxiv created 2021/09/17 · arxiv updated 2021/09/20 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

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 Λ_p(ℓ) 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 Λ_p(ℓ₁),Λ_p(ℓ₂) and compute bounds for it. We also study the number of edges in common between the graphs Λ_p(ℓ₁),Λ_p(ℓ₂).

Related

• Supersingular Isogeny Graphs from Algebraic Modular Curves
• Distribution of cycles in supersingular ℓ-isogeny graphs
• Cycles and Cuts in Supersingular L-Isogeny Graphs
• Double-orientations on supersingular isogeny graphs
• The Spine of a Supersingular ℓ-Isogeny graph