Generalised Erdős distance theory on graphs

2025/05/10 by Sean Dewar, Nóra Frankl, Dewar, Sean +9
Engineering · Computer Science · #Structural Analysis and Optimization #Computational Geometry and Mesh Generation #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2505.06590

Abstract

The famous Erdős distinct distances problem asks the following: how many distinct distances must exist between a set of n points in the plane? There are many generalisations of this question that ask one to consider different spaces and metrics, or larger structures of points. We bring these problems into a common framework using the concept of g-rigidity. Specifically, if G=(V,E) is a (hyper)graph, g is a map assigning polynomial measurements to the edges of G and f_g,G(P^V) gives the set of g-distinct realisations of the g-rigid graph G, where vertices must lie in a point set P, our main results describe sharp lower bounds for the size of |f_g,G(P^V)|. This allows us to obtain results for pseudo-Euclidean metrics, ℓ_p metrics, dot-product problems, matrix completion problems, and symmetric tensor completion problems. In addition, we use the recent work of Alon, Bucić and Sauermann along with a simple colouring argument to prove that the number of ‖ ⋅‖-distinct realisations of a graph G=(V,E) within a d-dimensional point set P is at least Ω(\frac|P|^|V|-1(log |P|)² ) for almost all d-norms. Our methods here also provide a short proof that the unit distance conjecture implies the pinned distance conjecture.

Citations

• On the Genus of One Degree of Freedom Planar Linkages via Tropical Geometry
• Irreducible components of sets of points in the plane that satisfy distance conditions
• Unit and distinct distances in typical norms
• Convexity, Superquadratic Growth, and Dot Products
• On discrete values of bilinear forms
• Infinitesimal rigidity for non-Euclidean bar-joint frameworks
• On the number of classes of triangles determined by N points in \R²
• On the Minkowski distances and products of sum sets
• Rigidity of Frameworks Supported on Surfaces
• The number of unit distances is almost linear for most norms
• Uniqueness of Low-Rank Matrix Completion by Rigidity Theory
• Some notes on the equivalence of first-order rigidity in various geometries

Related

• Finite point configurations in the plane, rigidity and Erdos problems
• Unit and distinct distances in typical norms
• Erdős's unit distance problem and rigidity
• Determining a Points Configuration from a Subset of the Pairwise Distances
• A new bound on Erdős distinct distances problem in the plane over prime fields