Optimal Embeddings of Distance Transitive Graphs into Euclidean Spaces
Frank Vallentin · arXiv (Cornell University) · 2005
ABSTRACT. In this paper we give an explicit formula for the least distortion embedding of a distance transitive graph into Euclidean space. We use this formula for finding least distortion embeddings for important examples: Hamming graphs, Johnson graphs, and Grassmann graphs. Our technique involves semidefinite programming and exploiting symmetry to simplify the optimization problem so that the question of finding the least distortion is reduced to an analytic question about orthogonal polynomials. 1.