Low-distortion embeddings of graphs with large girth

DOI10.1016/J.JFA.2012.01.020zbMATH Open1244.46036arXiv1108.2542OpenAlexW2962813142MaRDI QIDQ413201FDOQ413201

Authors: Mikhail Ostrovskii 

Publication date: 4 May 2012

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

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).

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

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

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)

Cites Work

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

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)