2025/07/03 by Dylan J. Altschuler, Konstantin Tikhomirov, Altschuler, Dylan J. +1
Mathematics · #Analytic and geometric function theory #Combinatorics (math.CO) #FOS: Mathematics #Functional Analysis (math.FA) #Geometric and Algebraic Topology #Geometry and complex manifolds #Metric Geometry (math.MG)
paper · pdf · doi:10.48550/arxiv.2507.02785
openalex publication_date 2025/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The metric dimension reduction modulus kαn(ℓ_∞) is the smallest k such that every n--point metric space can be embedded into some k-dimensional normed space, with bi--Lipschitz distortion at most α. Determining sharp asymptotics for kαn(ℓ_∞) is a fundamental task in metric geometry, with α=Θ(log n) bearing particular interest. A line of advances over the past decades has led to an upper bound on kαn(ℓ_∞) for α= Ω(log n), but a matching lower bound has remained open. We close this gap, establishing: for every fixed β> 0, kαn(ℓ_∞) =Θ(\fraclog nlog(\fracαlog n+1)) for every α≥ βlog n. This resolves a question from Naor's 2018 ICM plenary lecture. Our result is obtained by characterizing the minimum dimension d for which, with high probability, a random regular graph admits an α--embedding into some d--dimensional normed space.