Distinct distances determined by subsets of a point set in space (Q808426)

Zu \(p,q\in {\mathbb{R}}^d\) sei \(D(p,q)\) ihr euklidischer Abstand. Ist \(S\) eine endliche Menge des \({\mathbb{R}}^d\), so sei \(D(S)\) die Menge der verschiedenen Abstände von Punkten p,q\(\in S\), \(p\neq q\). Sei nun \(N_n\subset {\mathbb{R}}^d\) eine \(n\)-elementige Menge und \(P_k(N)\) die Menge der \(k\)-elementigen Teilmengen von \(N_n\). Ferner sei \(h\in {\mathbb{N}}\) und damit sei \(q(N_n,k,h)\) die Anzahl der \(k\)-elementigen Mengen \(S_k\subset N\) mit \(D(S_h)\geq h\). Trivial ist \(q(N_nk,h)\leq \binom{n}{k}\). Sei \(f=f(d,k)\) die größte Zahl h,derart daß \[ \lim_{n\to \infty}\left[q(N_n,k,h)/\binom{n}{k}\right]=1 \] gilt für alle Mengenfolgen \((N_n)_{n\in {\mathbb{N}}}\) n-elementiger Mengen \(N_n\). f(d,k) ist also die größte Zahl h derart, daß für großes \(n\) in fast allen \(k\)-elementigen Teilengen einer \(n\)-elementigen Menge mindestens \(h\) verschiedene Abstände vorkommen. Das Hauptresultat der Arbeit ist die explizite Bestimmung von \(f(d,k)\). Trivial ist \(f(1,k)=f(2,k)=\binom{k}{2}\). Für \(d\geq 3\) ergibt sich zunächst eine explizite obere Schranke \(g(d,h)\) aus einem Beispiel von Lenz. Mit Hilfe von graphentheoretischen Methoden wird \(g(d,k)\geq f(d,k)\) gezeigt. Eine Verfeinerung der Problemstellung geht auf Erdős und Purdy zurück: Man finde zu gegebenem \(i\), \(0<i\leq \binom{k}{2}\) asymptotische Resultate über die maximale Anzahl von \(k\)-elementigen Teilmengen \(S_k\) \(n\)-elementiger Mengen mit \(D(S_k)\leq i\). Für dieses Problem gibt es kaum Ergebnisse. Die Autoren zeigen für den Fall \(d=2\) das folgende Resultat: Sei \(k=o(n^{1/7})\). Dann haben für genügend großes \(n\) fast alle \(k\)-elementigen Teilmengen einer \(n\)-elementigen Menge \(\binom{k}{2}\) verschiedene Abstände.