# Ramanujan Graphs and the Spectral Gap of Supercomputing Topologies

arXiv: https://arxiv.org/abs/1909.11694 · HTML: https://mlsanity.com/paper/1909.11694/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [Seven open problems in applied combinatorics](https://mlsanity.com/paper/2303.11464/) (2023)

## Abstract (arXiv)

Graph eigenvalues play a fundamental role in controlling structural properties, such as bisection bandwidth, diameter, and fault tolerance, which are critical considerations in the design of supercomputing interconnection networks. This motivates considering graphs with optimal spectral expansion, called Ramanujan graphs, as potential candidates for interconnection networks. In this work, we explore this possibility by comparing Ramanujan graph properties against those of a wide swath of current and proposed supercomputing topologies. We derive analytic expressions for the spectral gap, bisection bandwidth, and diameter of these topologies, some of which were previously unknown. We find the spectral gap of existing topologies are well-separated from the optimal achievable by Ramanujan topologies, suggesting the potential utility of adopting Ramanujan graphs as interconnection networks.