Mathematics – Combinatorics
Scientific paper
2011-08-24
Mathematics
Combinatorics
17 pages
Scientific paper
Let $S$ be a set of $n$ points in $d$-dimensional Euclidean space. Assign to each $x\in 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\"os and Pach (1988) introduced the extremal quantity $f_d(n)=\max\sum_{x\in S}e_r(x,S)$, where the maximum is taken over all $n$-point sets $S$ in $d$-dimensional space and all assignments $r\colon S\to(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, which improves on previous results of Avis, Erd\"os and Pach (1988) and Erd\"os and Pach (1990). Then we prove a stability result for $d\geq 4$, asserting that if $(S,r)$ with $|S|=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 maximise the number of unit distance pairs with $r\equiv 1$, with some exceptions in dimension 4. Analogous results hold for the furthest neighbour digraph, where $r$ is fixed to be $r(x)=\max_{y\in S} |xy|$ for $x\in S$.
No associations
LandOfFree
Favourite distances in high dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Favourite distances in high dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Favourite distances in high dimensions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-377556