# A spectral gap precludes low-dimensional embeddings

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2016.

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

- [Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphs](https://mlsanity.com/paper/2504.08216/) (2025)
- [Distance-Preserving Embeddings in Inhomogeneous Random Graphs](https://mlsanity.com/paper/2607.10074/) (2026)

## Abstract (arXiv)

We prove that there is a universal constant C>0 with the following property. Suppose that n∈ mathbbN and that mathsfA=(aij)∈ Mn(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of mathsfA by λ2(mathsfA). Then for it any finite-dimensional normed space (X,|·|) we have  forall, x1,ldots,xn∈ X,qquad dim(X)≥ frac12 expleft(Cfrac1-λ2(mathsfA)√nbigg(fracsumi=1nsumj=1n|xi-xj|2sumi=1nsumj=1naij|xi-xj|2bigg)frac12right).  This implies that if an n-vertex O(1)-expander embeds with average distortion D≥ 1 into X, then necessarily dim(X)gtrsim nc/D for some universal constant c>0, thus improving over the previously best-known estimate dim(X)gtrsim (log n)2/D2 of Linial, London and Rabinovich, strengthening a theorem of Matouvsek, and answering a question of Andoni, Nikolov, Razenshteyn and Waingarten.