Finite point configurations in the plane, rigidity and Erd\H os problems

A. Iosevich ; J. Passant

Informatics and Automation, Harmonic analysis, approximation theory, and number theory, Tome 303 (2018), pp. 142-154

Résumé

For a finite point set $E\subset \mathbb {R}^d$ and a connected graph $G$ on $k+1$ vertices, we define a $G$‑framework to be a collection of $k+1$ points in $E$ such that the distance between a pair of points is specified if the corresponding vertices of $G$ are connected by an edge. We consider two frameworks the same if the specified edge-distances are the same. We find tight bounds on such distinct-distance drawings for rigid graphs in the plane, deploying the celebrated result of Guth and Katz. We introduce a congruence relation on a wider set of graphs, which behaves nicely in both the real-discrete and continuous settings. We provide a sharp bound on the number of such congruence classes. We then make a conjecture that the tight bound on rigid graphs should apply to all graphs. This appears to be a hard problem even in the case of the nonrigid $2$‑chain. However, we provide evidence to support the conjecture by demonstrating that if the Erdős pinned-distance conjecture holds in dimension $d$, then the result for all graphs in dimension $d$ follows.