On the Distortion of Embedding Perfect Binary Trees into Low-Dimensional Euclidean Spaces

Overview

We study the distortion of an optimal embedding of a perfect binary tree into a Euclidean space with a fixed number of dimensions. The distortion is a characteristic of the embedding, describing to what extend there is a correspondence between the natural metric on the graph and the induced Euclidean metric on its image. The optimal embedding of a graph is the one with the minimal distortion. We obtain an estimation of the lower bound of the distortion by using a volume argument and also present a particular embedding, showing that the value of the lower bound of the distortion is achievable up to a constant, independent of the number of vertices of the perfect binary tree.

Awards (2)

• Fourth Award of $500 $500
• American Mathematical Society: Certificate of Honorable Mention

Competition history

• ISEF 2017 Mathematics · Entry MATH003

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.