Large almost-equidistant sets from triangle-free strongly regular graphs

A set of points in ℝᵈ is almost-equidistant if among any three of them some two are at distance 1. Let f(d) be the largest size of an almost-equidistant set in ℝᵈ. The best lower bound previously recorded for every d ≥ 10 was f(d) ≥ 2d + 4, and the only structured ingredient in the literature was the 16-point set of Larman and Rogers in ℝ⁵ built from the Clebsch graph. We observe that every regular triangle-free graph on n vertices whose second largest eigenvalue λ₂ > 0 has multiplicity m yields an almost-equidistant set of n points on a sphere in ℝⁿ⁻¹⁻ᵐ, and that two spherical almost-equidistant sets can be combined by an orthogonal direct sum whenever their squared radii sum to 1. Applied to the Hoffman–Singleton, Gewirtz, M₂₂ and Higman–Sims graphs, and complemented by an extension lemma based on Delsarte-tight cocliques, this gives f(10) ≥ 26, f(20) ≥ 58, f(21) ≥ 78, f(22) ≥ 100, f(22 + j) ≥ 100 + 2j (1 ≤ j ≤ 8), f(31) ≥ 120, hence f(d) > 2d + 4 for all 20 ≤ d ≤ 57, and f(22) ≥ 100 > 4.5 · 22. The Higman–Sims set is a two-distance almost-equidistant set of 100 points in ℝ²², answering a question of Polyanskii for n = 100. All constructions are certified by an exact, dependency-free verification script. The authors are listed in alphabetical order and contributed equally.