Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 794.52004
Autor: Erdös, Paul; Füredi, Zoltán; Pach, János; Ruzsa, Imre Z.
Title: The grid revisited. (In English)
Source: Discrete Math. 111, No.1-3, 189-196 (1993).
Review: Diese Arbeit bezieht sich auf die Arbeit von P. Erdös [Ann. Math. Mon. 53, 248-250 (1946; Zbl 060.34805)]. Die originale Fragestellung wurde hier in einer verallgemeinerten Form aufgeschrieben: Sei eine Punktmenge P = {p1,p2,...,pn} in einem metrischen Raum M\supseteq P gegeben. Die Aufgabe ist die Bestimmung (oder die Abschätzung) des Maximums fM(n) des Vorkommens einer gegebenen Entfernung bzw. der kleinsten Zahl gM(n) verschiedener Entfernungen in einer Menge P, wobei fM(n) = max\max\alpha > 0 | {pi,pj}: d(pi,pj) = \alpha| bzw. gM(n) = max | {d(pi,pj): 1 \leq i < j \leq n}| ist.
Die Verfasser beweisen die folgenden Sätze:
1. Wenn d \geq 4 und n > 2 sind, und P auf einer Sphäre Sd-1 liegt, so existiert immer eine Konstante cd, womit die folgende Abschätzung gS(n) = g(P) \leq c4 {n\over log log n} falls d = 4 bzw. gS(n) = g(P) \leq cdn2/(d-2) falls d > 4 gilt.
2. Wenn n eine willkürliche natürliche Zahl ist, so existiert immer eine Konstante c, wobei eine Menge P aus n Punkten in der Ebene -- in einer allgemeinen Lage -- so gegeben werden kann, daß die folgende Abschätzung g(P) \leq n 2c\sqrt{log n} gilt.
3. Zu jedem C > 0 gehört je eine ganze Zahl n0 = n0(C) so, daß mindestens Cn Vektoren in der Ebene durch jede Menge P aus n Punkten (in einer allgemeinen Lage) bestimmt werden, falls n \geq n0 ist.
4. Zu einer willkürlichen Zahl \epsilon > 0 gehört die Zahl C = C(\epsilon) mit der folgenden Eigenschaft: Falls die Menge P der Cn Punkte auf einem Kreisbereich vom Radius n eingelagert werden kann, wobei die Entfernungen jeder beiden Punkte nicht kleiner als 1 sind, so -- zu jedem Winkel \alpha(0 \leq \alpha \leq 2\pi) -- existieren drei Punkte von P, die einen solchen Winkel bestimmen, dessen Größe sich von \alpha höchstens mit \epsilon unterscheidet.
Reviewer: I.Vermes (Budapest)
Classif.: * 52C10 Erdoes problems and related topics of discrete geometry
Keywords: Erdös problems
Citations: Zbl 060.34805
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag