Satz von Beck (Geometrie)

In der diskreten Geometrie bezeichnet der Satz von Beck verschiedene Ergebnisse, von denen zwei im Folgenden aufgeführt werden. Beide erschienen zusammen mit einigen anderen wichtigen Sätzen in einer bekannten Arbeit von József Beck . ^{[ 1 ]} Die beiden unten beschriebenen Ergebnisse betreffen hauptsächlich untere Schranken für die Anzahl der Geraden, die durch eine Punktmenge in der Ebene bestimmt werden . (Jede Gerade, die mindestens zwei Punkte einer Punktmenge enthält, heißt durch diese Punktmenge bestimmt .)

Der Satz von Erdős-Beck ist eine Variation eines klassischen Ergebnisses von L. M. Kelly und W. O. J. Moser ^{[ 2 ],} das Konfigurationen von n Punkten betrifft, von denen höchstens n  −  k kollinear sind, für ein 0 <  k  <  O ( √n ). Sie zeigten, dass, wenn n im Verhältnis zu k hinreichend groß ist , die Konfiguration mindestens kn  − (1/2)( 3k  + 2)( k  − 1) Geraden aufspannt. ^{[ 3 ]}

Elekes und Csaba Toth stellten fest, dass sich der Satz von Erdős-Beck nicht ohne Weiteres auf höhere Dimensionen übertragen lässt. ^{[ 4 ]} Betrachten wir beispielsweise eine Menge von 2ⁿ Punkten im R^³ , die alle auf zwei windschiefen Geraden liegen . Angenommen, jede dieser beiden Geraden ist mit n Punkten inzident. Eine solche Punktkonfiguration spannt nur 2 ⁿ Ebenen auf. Daher reicht eine triviale Erweiterung der Hypothese auf Punktmengen im R^{^d} nicht aus, um das gewünschte Ergebnis zu erzielen.

Dieses Ergebnis wurde zuerst von Erdős vermutet und von Beck bewiesen. (Siehe Satz 5.2 in ^{[ 1 ]} )

Sei S eine Menge von n Punkten in der Ebene. Wenn höchstens n  −  k Punkte auf einer Geraden für ein 0 ≤  k  <  n  − 2 liegen, dann existieren Ω( nk ) Geraden, die durch die Punkte von  S bestimmt werden .

Der Satz von Beck besagt, dass endliche Mengen von Punkten in der Ebene in eines von zwei Extremen fallen; eines, bei dem ein großer Anteil der Punkte auf einer einzigen Geraden liegt, und eines, bei dem eine große Anzahl von Geraden benötigt wird, um alle Punkte zu verbinden.

Obwohl in Becks Arbeit nicht erwähnt, ergibt sich dieses Ergebnis aus dem Satz von Erdős-Beck . ^{[ 5 ]}

Der Satz behauptet die Existenz positiver Konstanten C und K , sodass für beliebige n Punkte in der Ebene mindestens eine der folgenden Aussagen wahr ist:

1. Es gibt eine Gerade, die mindestens n / C der Punkte enthält.
2. Es gibt mindestens Geraden, von denen jede mindestens zwei der Punkte enthält.${\displaystyle n^{2}/K}$

In Becks ursprünglicher Argumentation ist C gleich 100 und K eine nicht näher spezifizierte Konstante; es ist nicht bekannt, welche optimalen Werte C und K haben.

Der Beweis des Satzes von Beck lässt sich wie folgt führen. Betrachten wir eine Menge P von n Punkten in der Ebene. Sei j eine positive ganze Zahl. Wir sagen, dass ein Punktepaar A , B in der Menge P j-zusammenhängend ist , wenn die Gerade, die A und B verbindet, zwischen und Punkten von P (einschließlich A und B ) liegt. ${\displaystyle 2^{j}}$${\displaystyle 2^{j+1}-1}$

Nach dem Satz von Szemerédi-Trotter ist die Anzahl solcher Geraden wie folgt gegeben: Gegeben sei die Menge P von n Punkten und die Menge L aller Geraden, die von Paaren von Punkten aus P aufgespannt werden und mindestens Punkte aus P enthalten . Da keine zwei Punkte auf zwei verschiedenen Geraden liegen können , ist die Anzahl der Inzidenzen zwischen P und L nach dem Satz von Szemerédi-Trotter höchstens . Alle Geraden, die j zusammenhängende Punkte verbinden, liegen ebenfalls in L und tragen jeweils mindestens zu den Inzidenzen bei. Daher ist die Gesamtzahl solcher Geraden . ${\displaystyle O(n^{2}/2^{3j}+n/2^{j})}$${\displaystyle 2^{j}}$${\displaystyle |L|\cdot {2^{j} \choose 2}\leq {n \choose 2}}$${\displaystyle O(n^{2}/2^{2j}+n)}$${\displaystyle 2^{j}}$${\displaystyle O(n^{2}/2^{3j}+n/2^{j})}$

Da jede solche Gerade Paare von Punkten miteinander verbindet , sehen wir, dass höchstens Paare von Punkten j -zusammenhängend sein können. ${\displaystyle \Omega (2^{2j})}$${\displaystyle O(n^{2}/2^{j}+2^{j}n)}$

Sei nun C eine große Konstante. Durch Summieren der geometrischen Reihe sehen wir, dass die Anzahl der Paare von Punkten, die j -zusammenhängend sind, für ein j, das die Bedingung erfüllt, höchstens beträgt . ${\displaystyle C\leq 2^{j}\leq n/C}$${\displaystyle O(n^{2}/C)}$

Andererseits ist die Gesamtzahl der Paare gleich . Wählt man C groß genug, so findet man mindestens Paare (beispielsweise), die für kein j- zusammenhängendes Paar existieren . Die Geraden, die diese Paare verbinden, verlaufen entweder durch weniger als 2 C Punkte oder durch mehr als n / C Punkte. Trifft Letzteres auch nur auf eines dieser Paare zu, so ist die erste Aussage des Satzes von Beck bewiesen. Daher kann man annehmen, dass alle Paare durch Geraden verbunden sind, die durch weniger als 2 C Punkte verlaufen . Jede dieser Geraden kann jedoch höchstens j Punktepaare verbinden. Somit muss es mindestens j Geraden geben, die mindestens zwei Punkte verbinden, und die Behauptung folgt durch Setzen von . ${\displaystyle {\frac {n(n-1)}{2}}}$${\displaystyle n^{2}/4}$${\displaystyle C\leq 2^{j}\leq n/C}$${\displaystyle n^{2}/4}$${\displaystyle C(2C-1)}$${\displaystyle n^{2}/4C(2C-1)}$${\displaystyle K=4C(2C-1)}$