Cited By
View all- Vallentin FMoustrou P(2023)Least distortion Euclidean embeddings of flat toriProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597147(13-23)Online publication date: 24-Jul-2023
Optimal distortion embeddings of distance regular graphs into Euclidean spaces
Pages 95 - 104
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.
References
[1]
Bannai, E. and Ito, T., Algebraic Combinatorics I: Association Schemes. 1984. Benjamin/Cummings, Menlo Park, CA.
[2]
Brouwer, A.E., Cohen, A.M. and Neumaier, A., Distance-Regular Graphs. 1989. Springer-Verlag, Berlin.
[3]
Bourgain, J., On Lipschitz embeddings of finite metric spaces in Hilbert spaces. Israel J. Math. v52. 46-52.
[4]
Enflo, P., On the nonexistence of uniform homeomorphisms between Lp-spaces. Ark. Mat. v8. 103-105.
[5]
Goemans, M.X. and Rendl, F., Semidefinite programs and association schemes. Computing. v63. 331-340.
[6]
Indyk, P., Algorithmic applications of low-distortion geometric embeddings. In: 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 10-33.
[7]
Linial, N., London, E. and Rabinovich, Y., The geometry of graphs and some of its algorithmic applications. Combinatorica. v15. 215-246.
[8]
Linial, N. and Magen, A., Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders. J. Combin. Theory Ser. B. v79. 157-171.
[9]
Linial, N., Finite metric-spaces---Combinatorics, geometry and algorithms. In: Proceedings of the International Congress of Mathematicians, vol. III, pp. 573-586.
[10]
Matousek, J., Lectures on Discrete Geometry. 2002. Springer-Verlag, New York.
[11]
Vandenberghe, L. and Boyd, S., Semidefinite Programming. SIAM Rev. v38. 49-95.
Index Terms
- Optimal distortion embeddings of distance regular graphs into Euclidean spaces
Recommendations
Edge-distance-regular graphs are distance-regular
A graph is edge-distance-regular when it is distance-regular around each of its edges and it has the same intersection numbers for any edge taken as a root. In this paper we give some (combinatorial and algebraic) proofs of the fact that every edge-...
The least Euclidean distortion constant of a distance-regular graph
AbstractIn 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 ...
Edge-distance-regular graphs
Edge-distance-regularity is a concept recently introduced by the authors which is similar to that of distance-regularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph @C with adjacency matrix A ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier Inc. © 2007.
Publisher
Academic Press, Inc.
United States
Publication History
Published: 01 January 2008
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Jan 2025
Other Metrics
Citations
Cited By
View all- Vallentin FMoustrou P(2023)Least distortion Euclidean embeddings of flat toriProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597147(13-23)Online publication date: 24-Jul-2023