On the Distortion of Embedding Perfect Binary Trees into Low-Dimensional Euclidean Spaces
ISEF · 2017 Mathematics Fourth Award
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
Resources
Related projects
ISEF · 2016
Graph Rigidity in L1 and Kusner's Conjecture
ISEF · 2017
Bounds on the Metric Dimensions for Families of Planar Graphs
ISEF · 2023
Extremal Problems on the Steiner k-Distance and the Steiner k-Wiener Index
ISEF · 2017
A 6-Chromatic Unit Distance Graph in Space
ISEF · 2016
A New Upper Bound for the Steiner Ratio
ISEF · 2019
On the Application of Heat Diffusion across a Manifold for Dimensionality Reduction
ISEF · 2018
The Analogue of Szemeredi's Theorem for Rectangles, n x n Lattice, Cuboid and n-Orthotope
ISEF · 2016
Embedding a Flat Torus in Three Dimensional Euclidean Space
Closest projects by meaning, across every fair and year in the corpus.
Browse more like this
Source: Regeneron International Science and Engineering Fair