Girth and Euclidean distortion

DOI10.1007/S00039-002-8251-YMaRDI QIDQ1606019zbMATH OpenOpenAlexFDO

Authors Nathan Linial, Avner Magen, Assaf Naor

Publication date 29 July 2002

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00039-002-8251-y

zbMATH Keywords

quadratic programmingMarkov typeEuclidean distortiongraph metricsPoincaré-type inequalities

Mathematics Subject Classification ID

Quadratic programming (90C20) Markov processes (60J99) Distance in graphs (05C12)

Recommendations

• Low-distortion embeddings of graphs with large girth
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
• scientific article; zbMATH DE number 1954393

Cited in

(31)

• Markov type and threshold embeddings
• Invariant Semidefinite Programs
• Markov type of Alexandrov spaces of non-negative curvature
• scientific article; zbMATH DE number 7378741 (Why is no real title available?)
• CAT(0) spaces and expanders.
• Finite flat spaces
• \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs
• Low-distortion embeddings of graphs with large girth
• Approximate Moore graphs are good expanders
• Euclidean upgrading from segment lengths
• Expander graphs -- both local and global
• An introduction to the Ribe program
• Diameters, distortion, and eigenvalues
• Expander graphs and their applications
• Spectral dimension, Euclidean embeddings, and the metric growth exponent
• Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
• Chemical subdiffusivity of critical 2D percolation
• Speed of random walks, isoperimetry and compression of finitely generated groups
• \(L_p\) compression, traveling salesmen, and stable walks.
• Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• The wreath product of $\mathbb {Z}$ with $\mathbb {Z}$ has Hilbert compression exponent $\frac {2}{3}$
• Spectral properties of balanced trees and dendrimers
• Markov type constants, flat tori and Wasserstein spaces
• Least distortion Euclidean embeddings of flat tori
• scientific article; zbMATH DE number 6478511 (Why is no real title available?)
• Snowflake universality of Wasserstein spaces
• 2-complexes with large 2-girth
• Metric \(X_{p}\) inequalities
• Umbel convexity and the geometry of trees
• An average John theorem

This page was built for publication: Girth and Euclidean distortion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1606019)