Favorite Distances in High Dimensions

Konrad J. Swanepoel ()
Additional contact information
Konrad J. Swanepoel: London School of Economics and Political Science, Department of Mathematics

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 499-519 from Springer

Abstract: 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: $${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.$$ The implied constants are absolute. This improves on previous results of Avis, Erdős, and Pach (1988) and Erdős and Pach (1990). 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.

Keywords: Favorite Distance; Digraph; Unit Distance Graph; Rich Circles; Diameter Pair (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_27

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_27

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().