Optimal distortion embeddings of distance regular graphs into Euclidean spaces

DOI10.1016/J.JCTB.2007.06.002MaRDI QIDQ2464155zbMATH OpenOpenAlexFDO

Authors Frank Vallentin

Publication date 10 December 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

distance regular graphsEuclidean embeddingsfinite metric spacesorthogonal polynomialssemidefinite programming

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Association schemes, strongly regular graphs (05E30)

Abstract: In this paper we give a lower bound for the least distortion embedding of a distance regular graph into Euclidean space. We use the lower bound for finding the least distortion for Hamming graphs, Johnson graphs, and all strongly regular graphs. Our technique involves semidefinite programming and exploiting the algebra structure of the optimization problem so that the question of finding a lower bound of the least distortion is reduced to an analytic question about orthogonal polynomials.

Recommendations

• Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
• Distortion lower bounds for line embeddings
• The least Euclidean distortion constant of a distance-regular graph
• Girth and Euclidean distortion
• Lower bounds on the distortion of embedding finite metric spaces in graphs

Cites work

• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (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?)
• Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• Semidefinite Programming
• Semidefinite programs and association schemes
• The geometry of graphs and some of its algorithmic applications

Cited in

(9)

• A divide-and-conquer strategy for embedding a distance-net point set into \(E^ n\) and its application
• Girth and Euclidean distortion
• Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
• The least Euclidean distortion constant of a distance-regular graph
• Invariant Semidefinite Programs
• scientific article; zbMATH DE number 1890143 (Why is no real title available?)
• Least distortion Euclidean embeddings of flat tori
• Embedding and the first Laplace eigenvalue of a finite graph
• A semidefinite program for least distortion embeddings of flat tori into Hilbert spaces

This page was built for publication: Optimal distortion embeddings of distance regular graphs into Euclidean spaces

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