Low-distortion embeddings of graphs with large girth

DOI10.1016/J.JFA.2012.01.020MaRDI QIDQ413201zbMATH OpenOpenAlexFDO

Authors Mikhail Ostrovskii

Publication date 4 May 2012

Published in Journal of Functional Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.2542

zbMATH Keywords

distortion of embedding of a metric space into a Banach spacegirth of a graphgraph lifts

Mathematics Subject Classification ID

Distance in graphs (05C12) Noncommutative topology (46L85)

Abstract: The main purpose of the paper is to construct a sequence of graphs of constant degree with indefinitely growing girths admitting embeddings into $el{l}_1$ with uniformly bounded distortions. This result answers the problem posed by N. Linial, A. Magen, and A. Naor (2002).

Recommendations

• Girth and Euclidean distortion
• Low distortion embeddings of some metric graphs into Banach spaces
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• scientific article; zbMATH DE number 1954393

Cites work

• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1789916 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Coarse non-amenability and coarse embeddings
• Coarsely embeddable metric spaces without Property A
• Expansion properties of metric spaces
• Explicit construction of regular graphs without small cycles
• Explicit constructions of graphs without short cycles and low density codes
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Generating all graph coverings by permutation voltage assignments
• Girth and Euclidean distortion
• Graph theory
• Minors in lifts of graphs
• PROPERTY A AND GRAPHS WITH LARGE GIRTH
• Ramanujan graphs
• Random Lifts of Graphs: Edge Expansion
• The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space
• The geometry of graphs and some of its algorithmic applications
• \(L_{1}\) embeddings of the Heisenberg group and fast estimation of graph isoperimetry

Cited in

(5)

• Girth and Euclidean distortion
• Graphs with Large Girth Not Embeddable in the Sphere
• A linear-space algorithm for distance preserving graph embedding
• Logarithmic girth expander graphs of \(SL_n({\mathbb{F}}_p)\)
• An introduction to the Ribe program

This page was built for publication: Low-distortion embeddings of graphs with large girth

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