Unit distances and diameters in Euclidean spaces

DOI10.1007/S00454-008-9082-XMaRDI QIDQ1006401zbMATH OpenOpenAlexFDO

Publication date 24 March 2009

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.0213

Erdős-Simonovits stability theorem Erdős-Stone theorem frequent diameter problem Lenz construction unit distance problem

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

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, for all

n

sufficiently large, depending on d.

Review text

In the 1950's, Lenz noticed that in \(d\geq 4\) dimensions, taking two orthogonal planes in one point \(p\), and taking two circles centered at \(p\) in the respective planes, the distances between any two points from the two circles are the same. In any even dimension \(d\geq 4\) this construction can be extended to \(d/2\) pairwise orthogonal planes pairwise intersecting in the origin, taking all \(d/2\) circles of radius \(1/\sqrt{2}\). A finite point set from the \(d/2\) circles is called a \textit{Lenz configuration}. (A slightly modified definition yields Lenz configurations in odd dimension.) The main result of the paper is that for each \(d\geq 4\), there exists \(N(d)\), such that all extremal sets of \(n\geq N(d)\) points (with respect to the number of unit distances or diameters) are Lenz configurations. As a corollary, for all \(d\geq 6\) even dimension the \textit{exact} maximum number of unit distances is determined for all sufficiently large number of points (depending on the dimension); and the \textit{exact} maximum number of diameters for all \(d\geq 4\) even dimension is determined for all sufficiently large number of points (depending on the dimension). The proof techniques hinge on extremal graph theory, namely the Erdős-Stone theorem and Erdős-Simonovits stability theorem.

Recommendations

Cites work

Cited in

(30)

This page was built for publication: Unit distances and diameters in Euclidean spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1006401)