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.

Bibliographie

[1] Aronov B., Pach J., Sharir M., Tardos G., “Distinct distances in three and higher dimensions”, Comb. Probab. Comput., 13:3 (2004), 283–293 | DOI | MR | Zbl

[2] Asimow L., Roth B., “The rigidity of graphs”, Trans. Amer. Math. Soc., 245 (1978), 279–289 | DOI | MR | Zbl

[3] Borcea C., Streinu I., “The number of embeddings of minimally rigid graphs”, Discrete Comput. Geom., 31:2 (2004), 287–303 | DOI | MR | Zbl

[4] Chatzikonstantinou N., Iosevich A., Mkrtchyan S., Pakianathan J., Rigidity, graphs and Hausdorff dimension, E-print, 2017, arXiv: 1708.05919 [math.CA]

[5] Chung F. R. K., “The number of different distances determined by $n$ points in the plane”, J. Comb. Theory. Ser. A, 36:3 (1984), 342–354 | DOI | MR | Zbl

[6] Chung F. R. K., Szemerédi E., Trotter W. T., “The number of different distances determined by a set of points in the Euclidean plane”, Discrete Comput. Geom., 7:1 (1992), 1–11 | DOI | MR | Zbl

[7] Clarkson K. L., Edelsbrunner H., Guibas L. J., Sharir M., Welzl E., “Combinatorial complexity bounds for arrangements of curves and spheres”, Discrete Comput. Geom., 5:2 (1990), 99–160 | DOI | MR | Zbl

[8] Erdős P., “On sets of distances of $n$ points”, Amer. Math. Mon., 53 (1946), 248–250 | DOI | MR | Zbl

[9] Graver J., Servatius B., Servatius H., Combinatorial rigidity, Grad. Stud. Math., 2, Amer. Math. Soc., Providence, RI, 1993 | DOI | MR | Zbl

[10] Guth L., Katz N. H., “On the Erdős distinct distances problem in the plane”, Ann. Math. Ser. 2, 181:1 (2015), 155–190 | DOI | MR | Zbl

[11] Katz N. H., Tardos G., “A new entropy inequality for the Erdős distance problem”, Towards a theory of geometric graphs, Contemp. Math., 342, Amer. Math. Soc., Providence, RI, 2004, 119–126 | DOI | MR | Zbl

[12] Moser L., “On the different distances determined by $n$ points”, Amer. Math. Mon., 59:2 (1952), 85–91 | DOI | MR | Zbl

[13] Roth B., “Rigid and flexible frameworks”, Amer. Math. Mon., 88:1 (1981), 6–21 | DOI | MR | Zbl

[14] Solymosi J., Tóth Cs. D., “Distinct distances in the plane”, Discrete Comput. Geom., 25:4 (2001), 629–634 | DOI | MR | Zbl

[15] Solymosi J., Vu V., “Distinct distances in high dimensional homogeneous sets”, Towards a theory of geometric graphs, Contemp. Math., 342, Amer. Math. Soc., Providence, RI, 2004, 259–268 | DOI | MR | Zbl

[16] Solymosi J., Vu V. H., “Near optimal bounds for the Erdős distinct distances problem in high dimensions”, Combinatorica, 28:1 (2008), 113–125 | DOI | MR | Zbl

[17] Székely L. A., “Crossing numbers and hard Erdős problems in discrete geometry”, Comb. Probab. Comput., 6:3 (1997), 353–358 | DOI | MR | Zbl

[18] Tardos G., “On distinct sums and distinct distances”, Adv. Math., 180:1 (2003), 275–289 | DOI | MR | Zbl