Graph Rigidity in L1 and Kusner's Conjecture

Overview

Purpose of the Experiment: The maximum number of points that can be embedded in a metric space, such that the distance between any two points is equal, is known as its equilateral dimension. The 30-year old Kusner conjecture states that the equilateral dimension of Rn under the L1 metric (the “Manhattan”, or “taxicab” metric) is 2n. While it is easily seen that 2n is a lower bound on the equilateral dimension, there is currently only a loose upper bound of n·logn, and the conjecture is not known to hold in dimensions bigger than 4. In my work I present a new approach to this problem. Procedures Used: I generalize the notion of rigid graphs to non-Euclidean metrics and investigate different properties of this generalization. Using these new tools I investigated Kusner's conjecture from an original approach. Observation/Data/Results: I proved a lemma that holds in all dimensions and reduces the number of embeddings one needs to eliminate in order to prove that 2n is the equilateral dimension. I also proved the known case n=3 using the lemma. Conclusions/Applications: In my work I present a new approach to Kusner's conjecture by extending the notion of graph rigidity to non-Euclidean metrics. While previous proofs for n=3, n=4 used unscalable methods, my approach relies on a lemma that holds for all n, lending support to the idea that it could be extended to a general proof. I thus demonstrate the usefulness of generalizing graph rigidity for improving upon an open problem, and suggest that the emerging insights could be applied in the future to a variety of other problems.

Competition history

• ISEF 2016 Category not listed · Entry MATH030

Resources

• ISEF abstract page ↗

Related projects

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