Beck-tétel (geometria)

A Beck-tétel a kategóriaelméletben (névrokon) a Beck-féle Monadizability Theorem

A Beck-tétel a kombinatorikus geometria számos eredményének egyike , amelyek közül kettőt az alábbiakban adunk meg. Mindkét tétel, néhány más fontos tétellel együtt, Joseph Beck [1] jól ismert cikkében jelent meg . Az alábbiakban ismertetett két eredmény egy síkban lévő ponthalmaz által meghatározott egyenesek számának alsó határára vonatkozik . (Azt mondjuk, hogy egy halmaz legalább két pontját összekötő vonalat egy ponthalmaz határoz meg.)

Erdős-Beck tétel

Az Erdős-Beck tétel L.M. klasszikus eredményének egy változata. Kelly és W.O.J. Moser [2] n pont konfigurációjáról , amelyek közül legfeljebb n − k kollineáris valamilyen 0 < k < O (√ n ) számra. Megmutatták, hogy ha n elég nagy k -hoz képest , akkor a konfiguráció legalább kn − (1/2)(3 k + 2)( k − 1) sort tartalmaz [3] .

Elekes és Toz Csaba észrevette, hogy az Erdős-Beck-tétel nem terjed ki könnyen magasabb dimenziókra [4] . Vegyünk például egy 2 n pontból álló halmazt R 3 -ban , amely két egymást metsző egyenesen fekszik . Tegyük fel, hogy e két egyenes mindegyike n pontra esik. Ez a konfiguráció csak 2 n síkot fed le. Így a hipotézis triviális kiterjesztése R d ponthalmazokra nem elegendő a kívánt eredmény eléréséhez.

Az eredményt először Erdős sejtésként fejezte ki, és igazolta Beck tételét [5] .

tétel állítása

Legyen S egy n pontból álló halmaz a síkon. Ha 0 ≤ k < n - 2 esetén több mint n − k pont egyike sem esik ugyanazon az egyenesen , akkor van Ω( nk ) egyenes, amelyet S -ből származó pontok határoznak meg .

Bizonyítás

Beck-tétel

Beck tétele kimondja, hogy a síkban lévő véges ponthalmaz két szélső eset egyikébe esik. Az egyik esetben a pontok nagy része egy vonalon fekszik, a másik esetben az összes pont összekapcsolásához nagy számú vonal szükséges.

Bár a cikk nem említi, ez az eredmény az Erdős-Beck tételből következik [6].

tétel állítása

A tétel kimondja, hogy van két pozitív C és K állandó , amelyre a síkban tetszőleges számú n pontra igaz a következők egyike:

Van egy egyenes, amely legalább n / C pontot tartalmaz.
Legalább olyan vonalak vannak, amelyek mindegyike legalább két pontot tartalmaz. $n^{2}/K$

Beck eredeti cikkében a C értéke 100, és a K konstans értéke nincs megadva. C és K optimális értéke ismeretlen.

Bizonyítás

Beck tételét a következőképpen bizonyíthatja. Legyen P egy n pontból álló halmaz a síkon. Legyen j pozitív egész szám . Azt mondjuk, hogy egy P halmazban lévő A és B pont párja j-összefüggésben van , ha az A-t és B-t összekötő egyenes tartalmazza a -tól a P -beli pontig (beleértve A -t és B -t is ). ${\displaystyle 2^{j))$ $2^{j+1}-1$

A Szemedi-Trotter tételből következik, hogy az ilyen sorok száma egyenlő a következő okból. Legyen a P halmaz n pontból és az L halmaz minden olyan P halmaz pontpárjait összekötő egyenesből, amely a P halmaz legalább pontját tartalmazza . Vegye figyelembe, hogy mivel nem lehet két pont két különálló egyenesen. Most a Szemedi-Trotter tételt használjuk, ami azt jelenti, hogy a P és L közötti előfordulások száma nem haladja meg a -t . A j-vel összekapcsolt pontokat összekötő összes vonal szintén L -ben van , és minden vonalnak van legalább beesése. Így az ilyen sorok teljes száma . $O(n^{2}/2^{3j}+n/2^{j})$ ${\displaystyle 2^{j))$ ${\displaystyle |L|\cdot {2^{j} \choose 2}\leq {n \choose 2))$ $O(n^{2}/2^{2j}+n)$ ${\displaystyle 2^{j))$ $O(n^{2}/2^{3j}+n/2^{j})$

Mivel minden ilyen egyenes pontpárokat köt össze, ezért azt látjuk, hogy legfeljebb pontpárok lehetnek j -összekötve. $\Omega (2^{2j})$ $O(n^{2}/2^{j}+2^{j}n)$

Legyen most C kellően nagy állandó. A geometriai progressziót összegezve azt kapjuk, hogy néhány j -hez tartozó j összefüggő pontpárok száma nem haladja meg az egyenlőtlenséget . $C\leq 2^{j}\leq n/C$ $O(n^{2}/b\C)$

Másrészt a pontpárok teljes száma . Majd ha elég nagy C -t választunk , akkor legalább olyan párokat találhatunk (például), amelyek nem j -kapcsoltak egyikhez sem . Ezeket a pontokat összekötő vonalak, amelyek kevesebb, mint 2 C ponton vagy több, mint n / C ponton haladnak át . Ha az utolsó állítás legalább egy párra érvényes, akkor a Beck-tétel első állítása teljesül. Ekkor feltételezhetjük, hogy az összes párt olyan egyenesek kötik össze, amelyek kevesebb, mint 2 C ponton mennek át. Egy ilyen vonal azonban legfeljebb pontpárokat köthet össze. Ekkor legalább két pontot összekötő egyenesnek kell lennie , hogy a tétel kijelentését megkapjuk, ha elfogadjuk . ${\frac {n(n-1)}{2}}$ $n^{2}/4$ $C\leq 2^{j}\leq n/C$ $n^{2}/4$ $C(2C-1)$ $n^{2}/4C(2C-1)$ $K=4C(2C-1)$

Jegyzetek

↑ Beck, 1983 , p. 281–297.
↑ William OJ Moser . Letöltve: 2017. szeptember 10. Az eredetiből archiválva : 2016. október 5.. (határozatlan)
↑ Kelly és Moser, 1958 , p. 210–219.
↑ Elekes, Tóth, 2005 , p. 16–21.
↑ Beck, 1983 , p. 281–297 5.2. Tétel.
↑ A Beck-tételt úgy kapjuk meg, hogy k = n (1 − 1/ C ) és az Erdős-Beck tételt alkalmazzuk.

Irodalom

Beck J. A sík rácstulajdonságáról és Dirac, Motzkin és Erdős néhány problémájáról a kombinatorikus geometriában // Combinatorica. - 1983. - T. 3 . – S. 281–297 . - doi : 10.1007/BF02579184 .

Kelly LM, Moser WOJ Az n pont által meghatározott közönséges vonalak számáról // Kanada. J. Math .. - 1958. - T. 10 . - doi : 10.4153/CJM-1958-024-6 .
Elekes G., Tóth CD A nem túl degenerált hipersíkok előfordulásai // Proceedings of the twenty-first year symposium on Computational geometry. - Pisa, Olaszország: Éves Szimpózium a Számítógépes Geometriáról, 2005. - ISBN 1-58113-991-8 .