Wenige Steigungen

Wenige Steigungen
Proseminar: Beweise aus dem Buch, Maximilian Heininger
27.06.2015
1 Einleitung
Wie u.a. in ’Kapitel 10 - Geraden in der Ebene und Zerlegungen von Graphen’ im Buch
der Beweise gezeigt, folgt aus dem James J. Sylvester und Tibor Gallai zugeschriebenen
Satz 1: Für jede Anordnung von endlich vielen Punkten in der Ebene, die
nicht alle auf einer Geraden liegen, gibt es eine Gerade, die genau zwei der
Punkte enthält
ein weiteres, von Paul Erdõs und Nicolaas G. de Brujin im Jahr 1948 in deutlich allgemeinerer Form gezeigtes Resultat:
Satz 2: Sei P eine Menge von n ≥ 3 Punkten in der Ebene, die nicht alle
auf einer Geraden liegen. Dann besteht die Menge L der Geraden, die durch
mindestens zwei der Punkte in P gehen, aus mindestens n Geraden.
Da theoretisch viele der durch n Punkte definierten Geraden gleiche Steigungen besitzen könnten, ergibt sich aus diesen Ergebnissen die anschließende Fragestellung nach
der minimalen Anzahl der durch die Verbindungsgeraden von n Punkten definierten
Steigungen.
1.1 Vorüberlegung 1 - Ergebnisse von P.R. Scott
Definition (kn − F unktion): Sei Pn eine Menge von n nicht kollinearen Punkten in
der Ebene, zusammen mit der Menge aller Verbindungsgeraden dieser Punkte. Sei des
weiteren k(Pn ) die Anzahl der unterschiedlichen Steigungen, welche durch die Geraden
von Pn beschrieben werden. Bezeichne nun ℘ die Familie all solcher Mengen Pn , so ist
kn = min k(Pn )
Pn ∈℘
Für dieses Extremalproblem konnte Scott 1970 die folgenden Grenzen beweisen:
√
1
2 (1 + 8n − 7) ≤ kn ≤ n
Scott vermutete kn = n, konnte dies jedoch nur für konvexe Punktmengen beweisen.
1
1.2 Vorüberlegung 2 - Einfache Beispiele und Annahme
Da auch weitere Versuche keine besseren Konfigurationen liefern, liegt folgende, der
Vermutung von Scott ähnelnde Annahme nahe:
Satz 3: Wenn n ≥ 3 Punkte in der Ebene nicht alle auf einer Geraden
liegen, dann bestimmen sie mindestens n − 1 verschiedene Steigungen, wobei
der Extremfall von genau n − 1 Steigungen nur für ungerades n ≥ 5 möglich
ist.
Um diesen Satz im Folgenden zu beweisen, benötigen wir noch einen Ansatz, der das
schwer zugängliche geometrische Extremalproblem in ein besser zugängliches kombinatorisches Problem überführt.
1.3 Vorüberlegung 3 - Kombinatorisches Modell von Goodman und Pollack
Sei C = {P1 , ..., Pn } eine nummerierte Konfiguration von n Punkten in der euklidischen
Ebene und L eine gerichtete Linie, welche nicht senkrecht zu irgendeiner von 2 Punkten
aus C bestimmten Richtung steht. Wird C orthogonal auf L projiziert, so erhält man
eine Permutation von [1,n]. Eine Rotation von L führt immer dann zu einer neuen Permutation, wenn L eine Richtung senkrecht zu den durch die Punkte von C bestimmten
Richtungen durchschreitet.
2
Wählt man die Anfangsrichtung so, dass π0 = 123...n und dreht L um 180◦ gegen den
Uhrzeigersinn, so erhält man eine mit C assoziierte Folge von Permutationen
π0 → π1 → π2 → ... → πt−1 → πt
mit folgenden für den Beweis wichtigen Eigenschaften:
1. Die Folge beginnt mit π0 = 123...n und endet mit πt = n...321
2. Die Länge t entspricht der Anzahl der Steigungen der Punktkonfiguration C
3. In der Folge wird jedes Paar i < j genau einmal umgedreht
⇒ Jeder Einzelschritt besteht im Umdrehen von einem oder mehreren disjunkten
aufsteigenden Teilabschnitten der Permutation
Wird die Projektionsrichtung beliebig weiter gedreht, so erhält man eine in beide Richtungen unbegrenzte periodische Folge von Permutationen
... → π−1 → π0 → π1 → ... → πt−1 → πt → πt+1 → ... → π2t → ...
wobei für diese Folge dann zusätzlich gilt:
4. πi+t ist genau die Umkehrung der Permutation πi und πi+2t = πi , ∀i ∈ Z
5. ⇒ Die Einzelschritte der durch Drehung im Uhrzeigersinn erhaltenen Folge π0 →...→
π−t = πt entspricht gerade der Umkehrung der Einzelschritte der durch Drehung
gegen den Uhrzeigersinn erhaltenen Folge π0 →...→ πt
2 Beweis
2.1 Grundidee für gerade n
Gesucht ist die minimale Länge t einer Folge von Permutationen, welche die oben aufgeführten Eigenschaften besitzt. Dabei werden zunächst nur gerade n = 2m betrachtet.
Für den Beweis von Peter Ungar aus dem Jahr 1982 wird nun jede Permutation in der
Mitte durch eine imaginäre T rennlinie(:) in zwei Hälften der Größe m = n2 aufgeteilt.
z.B. π0 = 1... n2 :
n+2
2 ...n
Desweiteren definieren wir: Ein Permutationsschritt πi → πi+1 heißt
• Kreuzungsschritt der Ordnung d, wenn dabei 2d Ziffern auf die andere Seite
der Trennlinie wechseln (der umgedrehte Teilabschnitt läuft über die Trennlinie)
• Berührschritt, wenn dabei eine oder zwei an der Trennlinie gelegen Ziffern ihre
Position ändern, ohne auf die andere Seite der Trennlinie zu wechseln (umgedrehte
Teilabschnitte berühren die Trennlinie)
• Normalschritt, wenn er weder Kreuzungsschritt noch Berührschritt ist (umgedrehte Teilabschnitte berühren die Trennlinie nicht)
Die Schritte werden mit K(d), B und N abgekürzt.
3
2.1.1 Zusammenhänge zwischen K-,B- und N-Schritten
Aus der Tatsache, dass nur aufsteigende Teilabschnitte in einem Permutationsschritt
umgedreht werden können (3. Eigenschaft) sowie dem Zusammenhang der Einzelschritte
bei Umkehrung des Weges (5. Eigenschaft) folgt
• Zwischen zwei Kreuzungsschritten gibt es immer mindestens einen Berührschritt
• Zwischen einem Kreuzungsschritt der Ordnung d und dem nächsten Berührschritt
liegen immer mindestens d-1 Normalschritte
• Zwischen einem Berührschritt und dem nächsten Kreuzungsschritt der Ordnung d
liegen immer mindestens d-1 Normalschritte
2.1.2 Abschluss des Beweises
Wir betrachten nun eine Teilfolge der Länge t, welche mit einem Berührschritt beginnt,
und die Kreuzungsschritte K(di ) enthält. Da in dieser Teilfolge jedes Zeichen mindestens
einmal die Trennlinie überqueren muss folgt aus der Definition der Kreuzungsschritte
P
2di ≥ n
Aus obigen Zusammenhängen folgt, dass jeder Kreuzungsschritt in ein Muster vom Typ
B, N, ..., N , K(d), N, ..., N
|
{z
≥d−1
}
|
{z
≥d−1
}
der Länge 1 + (d − 1) + 1 + (d − 1) = 2d eingebettet ist.
Die Teilfolge besteht somit aus einer Folge solcher Abschnitte sowie evtl. zusätzlichen
Berührschritten, wodurch sich für ihre Länge t
t≥
P
2di ≥ n
ergibt, was den Beweis für gerade n abschließt.
2.2 Überlegung für ungerade n
Jede ’ungerade’ Menge von n = 2m + 1 Punkten besitzt eine ’gerade’ Teilmenge von
2m = n − 1 Punkten, welche mindestens n − 1 Steigungen besitzt. Das Hinzufügen eines
Punktes kann die Anzahl der Steigungen nur unverändert lassen oder erhöhen
⇒ Satz 3 gilt für alle n.
3 Literatur
(1) M. Aigner; G. M. Ziegler: Das BUCH der Beweise. Berlin, Springer Spektrum 2015
(2) P. R. Scott: On the sets of directions determined by n points, Amer. Math. Monthly 77 (1970),
502-505
(3) J. E. Goodman; R. Pollack: A combinatorial perspective on some problems in geometry, Congressus Numerantium 32 (1981), 383-394
(4) P. Ungar: 2N noncollinear points determine at least 2N directions, Combinatorial Theory, Ser.
A 33 (1983), 343-347
4

Download Report