The least Euclidean distortion constant of a distance-regular graph

DOI10.1016/J.DAM.2022.10.014MaRDI QIDQ2104939zbMATH OpenOpenAlexFDO

Authors Sebastian Cioaba, Himanshu Gupta, Ferdinand Ihringer, Hirotake Kurihara

Publication date 8 December 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

distance-regular graphseigenvalues of graphsEuclidean embeddinggraphs with classical parametersGrassmann graphsHermitian forms graphsleast distortionodd graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Association schemes, strongly regular graphs (05E30) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: In 2008, Vallentin made a conjecture involving the least distortion of an embedding of a distance-regular graph into Euclidean space. Vallentin's conjecture implies that for a least distortion Euclidean embedding of a distance-regular graph of diameter $d$, the most contracted pairs of vertices are those at distance $d$. In this paper, we confirm Vallentin's conjecture for several families of distance-regular graphs. We also provide counterexamples to this conjecture, where the largest contraction occurs between pairs of vertices at distance $d-1$. We suggest three alternative conjectures and prove them for several families of distance-regular graphs.

Recommendations

• scientific article; zbMATH DE number 782048
• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• The equidistant dimension of graphs
• On Euclidean distance matrices of graphs
• Distance regularity in direct-product graphs
• scientific article; zbMATH DE number 681028
• On the Cheeger constant for distance-regular graphs
• Diameter bounds for geometric distance-regular graphs
• On the least distance eigenvalue of a graph
• Some elementary inequalities for distance-regular graphs

Cites work

• \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs
• A partially ordered set and q-Krawtchouk polynomials
• Hermitian rank distance codes
• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (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
• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• The Euclidean distortion of generalized polygons
• The geometry of graphs and some of its algorithmic applications
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters

Cited in

(3)

• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• Least distortion Euclidean embeddings of flat tori
• A semidefinite program for least distortion embeddings of flat tori into Hilbert spaces

This page was built for publication: The least Euclidean distortion constant of a distance-regular graph

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