ACO The ACO Seminar (2022–2023)

October 6, 3:30pm, Wean 8220
Himanshu Gupta, University of Delaware
The least Euclidean distortion constant of a distance-regular graph


Embedding graphs into Euclidean spaces with least distortion is a topic well-studied in mathematics and computer science. Despite this research, there are just a few graphs for which the precise least distortion and a least distortion embedding is known. In 2008, Vallentin studied this problem for distance-regular graphs and obtained a lower bound for the least distortion of a distance-regular graph. In addition, he showed that this bound is tight for Hamming and Johnson graphs as well as strongly regular graphs and conjectured that his bound is always tight for distance-regular graphs. In this talk, we provide several counterexamples to this conjecture with diameter 4 and larger, but we also prove the conjecture for several families of distance-regular graphs. This is joint work with Sebastian M. Cioabă (University of Delaware), Ferdinand Ihringer (Ghent University), and Hirotake Kurihara (Yamaguchi University).

Back to the ACO home page Back to the ACO Seminar schedule