Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

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

Booth Id:



Finalist Names:
Ivanova, Dona-Maria (School: Star College Boys' High School)

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 Won:
Fourth Award of $500
American Mathematical Society: Certificate of Honorable Mention