Abstract:
For a finite point set E⊂Rd 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.
Citation:
A. Iosevich, J. Passant, “Finite point configurations in the plane, rigidity and Erdős problems”, Harmonic analysis, approximation theory, and number theory, Collected papers. Dedicated to Academician Sergei Vladimirovich Konyagin on the occasion of his 60th birthday, Trudy Mat. Inst. Steklova, 303, MAIK Nauka/Interperiodica, Moscow, 2018, 142–154; Proc. Steklov Inst. Math., 303 (2018), 129–139
\Bibitem{IosPas18}
\by A.~Iosevich, J.~Passant
\paper Finite point configurations in the plane, rigidity and Erd\H os problems
\inbook Harmonic analysis, approximation theory, and number theory
\bookinfo Collected papers. Dedicated to Academician Sergei Vladimirovich Konyagin on the occasion of his 60th birthday
\serial Trudy Mat. Inst. Steklova
\yr 2018
\vol 303
\pages 142--154
\publ MAIK Nauka/Interperiodica
\publaddr Moscow
\mathnet{http://mi.mathnet.ru/tm3955}
\crossref{https://doi.org/10.1134/S0371968518040118}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3920219}
\elib{https://elibrary.ru/item.asp?id=37045257}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2018
\vol 303
\pages 129--139
\crossref{https://doi.org/10.1134/S0081543818080114}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000460475900011}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85062615828}
Linking options:
https://www.mathnet.ru/eng/tm3955
https://doi.org/10.1134/S0371968518040118
https://www.mathnet.ru/eng/tm/v303/p142
This publication is cited in the following 3 articles:
T. Pham, S. Senger, T. D. Tran, “Distribution of pinned distance trees in the plane F2p”, Discrete Mathematics, 346:12 (2023), 113613
J. Passant, “On erdos chains in the plane”, Bull. Korean. Math. Soc., 58:5 (2021), 1279–1300
Rudnev M., “Note on the Number of Hinges Defined By a Point Set in Double-Struck Capital R-2”, Combinatorica, 40:5 (2020), 749–757