Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Favorite Distances in High Dimensions
verfasst von : Konrad J. Swanepoel
Erschienen in: Thirty Essays on Geometric Graph Theory
Verlag: Springer New York
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let S be a set of n points in \({\mathbb{R}}^{d}\). Assign to each x ∈ S an arbitrary distance r(x) > 0. Let e
r
(x, S) denote the number of points in S at distance r(x) from x. Avis, Erdős, and Pach (1988) introduced the extremal quantity \({f}_{d}(n) =\max \sum\limits_{\mathbf{x}\in S}{e}_{r}(\mathbf{x},S)\), where the maximum is taken over all n-point subsets S of \({\mathbb{R}}^{d}\) and all assignments \(r: S \rightarrow (0,\infty )\) of distances.
We give a quick derivation of the asymptotics of the error term of f
d
(n) using only the analogous asymptotics of the maximum number of unit distance pairs in a set of n points: The implied constants are absolute. This improves on previous results of Avis, Erdős, and Pach (1988) and Erdős and Pach (1990).
$${f}_{d}(n) = \left(1 - \frac{1} {\lfloor d/2\rfloor }\right){n}^{2}+\left\{\begin{array}{@{}l@{\quad }l@{}} \Theta (n) \quad &\text{ if}\ d\ \text{ is even,} \\ \Theta {((n/d))}^{4/3})\quad &\text{ if}\ d\ \text{ is odd.} \end{array} \right.$$
Then we prove a stability result for d ≥ 4, asserting that if (S, r) with \(\left\vert S\right\vert = n\) satisfies \({e}_{r}(S) = {f}_{d}(n) - o({n}^{2})\), then, up to o(n) points, S is a Lenz construction with r constant. Finally, we use stability to show that for n sufficiently large (depending on d), the pairs (S, r) that attain f
d
(n) are up to scaling exactly the Lenz constructions that maximize the number of unit distance pairs with r ≡ 1, with some exceptions in dimension 4.
Analogous results hold for the furthest-neighbor digraph, where r is fixed to be \(r(\mathbf{x}) {=\max }_{\mathbf{y}\in S}\vert \mathbf{x}\mathbf{y}\vert\) for x ∈ S.