Abstract
We show that the maximum number of unit distances or of diameters in a set of n points in d-dimensional Euclidean space is attained only by specific types of Lenz constructions, for all d≥4 and n sufficiently large depending on d. As a corollary, we determine the exact maximum number of unit distances for all even d≥6 and the exact maximum number of diameters for all d≥4 and all n sufficiently large depending on d.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Brass, P.: On the maximum number of unit distances among n points in dimension four. In: Bárány, I., et al. (eds.) Intuitive Geometry. Bolyai Soc. Mathematical Studies, vol. 6, pp. 277–290. Jànos Bolyai Math. Soc., Budapest (1997). See also the review of this paper in Mathematical Reviews MR 98j:52030
Bollobás, B.: Extremal Graph Theory. Academic Press, London (1978). Reprinted by Dover, Mineola (2004)
Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., Welzl, E.: Combinatorial complexity bounds for arrangements of curves and surfaces. Discrete Comput. Geom. 5, 99–160 (1990)
Erdős, P.: On sets of distances of n points. Am. Math. Mon. 53, 248–250 (1946)
Erdős, P.: On sets of distances of n points in Euclidean space. Magy. Tud. Akad. Mat. Kut. Int. Közl. 5, 165–169 (1960)
Erdős, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications, Proc. Sympos. Smolenice, 1963, pp. 29–36. Publ. House Czech. Acad. Sci., Prague (1964)
Erdős, P.: On some applications of graph theory to geometry. Can. J. Math. 19, 968–971 (1967)
Erdős, P.: On some new inequalities concerning extremal properties of graphs. In: Erdős, P., Katona, G. (eds.) Theory of Graphs, pp. 279–319. Academic Press, New York (1968)
Erdős, P.: Combinatorial problems in geometry and number theory. In: Relations between combinatorics and other Parts of Mathematics, Ohio State Univ., Columbus, OH, 1978. Proc. Sympos. Pure Math., vol. XXXIV, pp. 149–162. American Mathematical Society, Providence (1979)
Erdős, P.: On some metric and combinatorial geometric problems. Discrete Math. 60, 147–153 (1986)
Erdős, P.: Some of my favourite unsolved problems. In: A Tribute to Paul Erdős, pp. 467–478. Cambridge University Press, Cambridge (1990)
Erdős, P.: Some unsolved problems. In: Combinatorics, Geometry and Probability, Cambridge, 1993, pp. 1–10. Cambridge University Press, Cambridge (1997)
Erdős, P., Hickerson, D., Pach, J.: A problem of Leo Moser about repeated distances on the sphere. Am. Math. Mon. 96, 569–575 (1989)
Erdős, P., Pach, J.: Variations on the theme of repeated distances. Combinatorica 10, 261–269 (1990)
Erdős, P., Stone, A.H.: On the structure of linear graphs. Bull. Am. Math. Soc. 52, 1087–1091 (1946)
Füredi, Z., Simonovits, M.: Triple systems not containing a Fano configuration. Comb. Probab. Comput. 14, 467–484 (2005)
Grünbaum, B.: A proof of Vázsonyi’s conjecture. Bull. Res. Counc. Isr. Sect. A 6, 77–78 (1956)
Heppes, A.: Beweis einer Vermutung von A. Vázsonyi. Acta Math. Acad. Sci. Hung. 7, 463–466 (1957)
Hopf, H., Pannwitz, E.: Aufgabe Nr. 167. Jahresber. Dtsch. Math.-Verein. 43, 114 (1934)
Keevash, P., Sudakov, B.: The Turán number of the Fano plane. Combinatorica 25, 561–574 (2005)
Kupitz, Y.S., Martini, H., Wegner, B.: Diameter graphs and full equi-intersectors in classical geometries. In: IV International Conference in “Stochastic Geometry, Convex Bodies, Empirical Measures & Applications to Engineering Science,” vol. II, Tropea, 2001. Rend. Circ. Mat. Palermo (2) Suppl. No. 70, part II, pp. 65–74 (2002)
Martini, H., Soltan, V.: Antipodality properties of finite sets in Euclidean space. Discrete Math. 290, 221–228 (2005)
Mubayi, D., Pikhurko, O.: A new generalization of Mantel’s theorem to k-graphs. J. Comb. Theory (B) 97, 669–678 (2007)
Neaderhouser, C.C., Purdy, G.B.: On finite sets in E k in which the diameter is frequently achieved. Period. Math. Hung. 13, 253–257 (1982)
Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley, New York (1995)
Simonovits, M.: A method for solving extremal problems in graph theory. Stability Problems. In: Erdős, P., Katona, G. (eds.) Theory of Graphs, pp. 279–319. Academic Press, New York (1968)
Spencer, J., Szemerédi, E., Trotter, W., Jr.: Unit distances in the Euclidean plane. In: Graph theory and Combinatorics, Cambridge, 1983, pp. 293–303. Academic Press, London (1984)
Straszewicz, S.: Sur un problème géométrique de P. Erdős. Bull. Acad. Pol. Sci. Cl. III. 5, 39–40 (1957)
Sutherland, J.W.: Lösung der Aufgabe 167. Jahresber. Dtsch. Math.-Verein. 45, 33–35 (1935)
Swanepoel, K.J.: A new proof of Vázsonyi’s conjecture. J. Comb. Theory Ser. A doi: 10.1016/j.jcta.2007.08.006 (in press)
Swanepoel, K.J., Valtr, P.: The unit distance problem on spheres. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs. Contemporary Mathematics, vol. 342, pp. 273–279. American Mathematical Society, Providence (2004)
Székely, L.A.: Crossing numbers and hard Erdős problems in discrete geometry. Comb. Probab. Comput. 6, 353–358 (1997)
van Wamelen, P.: The maximum number of unit distances among n points in dimension four. Beitr. Algebra Geom. 40, 475–477 (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
This material is based upon work supported by the South African National Research Foundation.
Rights and permissions
About this article
Cite this article
Swanepoel, K.J. Unit Distances and Diameters in Euclidean Spaces. Discrete Comput Geom 41, 1–27 (2009). https://doi.org/10.1007/s00454-008-9082-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9082-x