Twierdzenie Becka (geometria)

Aby zapoznać się z teorią kategorii opracowaną przez innego autora, zobacz twierdzenie Becka o monadyczności .

W geometrii dyskretnej twierdzenie Becka jest dowolnym z kilku różnych wyników, z których dwa podano poniżej. Oba pojawiły się, wraz z kilkoma innymi ważnymi twierdzeniami, w dobrze znanej pracy Józsefa Becka . Dwa opisane poniżej wyniki dotyczą przede wszystkim dolnych granic liczby prostych wyznaczonych przez zbiór punktów na płaszczyźnie. (Mówi się, że każda linia zawierająca co najmniej dwa punkty zbioru punktów jest wyznaczona przez ten zbiór punktów.)

Twierdzenie Erdősa-Becka

Erdősa – Becka jest odmianą klasycznego wyniku LM Kelly'ego i WOJ Mosera, obejmującego konfiguracje n punktów, z których co najwyżej n - k jest współliniowych, dla niektórych 0 < k < O ( √ n ). Pokazali, że jeśli n jest wystarczająco duże w stosunku do k , to konfiguracja obejmuje co najmniej kn − (1/2)(3 k + 2)( k − 1) prostych.

Elekes i Csaba Toth zauważyli, że twierdzenie Erdősa – Becka nie daje się łatwo rozszerzyć na wyższe wymiary. Weźmy na przykład zbiór 2 n punktów w R ³ leżących na dwóch liniach skośnych . Załóżmy, że każda z tych dwóch prostych przypada na n punktów. Taka konfiguracja punktów obejmuje tylko 2 n płaszczyzn. Zatem trywialne rozszerzenie hipotezy dla zbiorów punktowych w Rd nie jest wystarczające do ^uzyskania pożądanego wyniku.

Wynik ten został po raz pierwszy przypuszczony przez Erdősa i udowodniony przez Becka. (Patrz Twierdzenie 5.2 w.)

Oświadczenie

Niech S będzie zbiorem n punktów na płaszczyźnie. Jeśli nie więcej niż n − k punktów leży na dowolnej prostej dla pewnych 0 ≤ k < n − 2, to istnieją proste Ω( nk ) określone przez punkty S .

Twierdzenie Becka

Twierdzenie Becka mówi, że skończone zbiory punktów na płaszczyźnie mieszczą się w jednej z dwóch skrajności; jeden, w którym duża część punktów leży na jednej linii, i taki, w którym do połączenia wszystkich punktów potrzebna jest duża liczba linii.

Chociaż nie wspomniano o tym w artykule Becka, wynik ten wynika z twierdzenia Erdősa-Becka .

Oświadczenie

Twierdzenie stwierdza istnienie dodatnich stałych C , K takich, że dla dowolnych n punktów na płaszczyźnie przynajmniej jedno z poniższych zdań jest prawdziwe:

1. Istnieje linia, która zawiera co najmniej n / C punktów.
2. Istnieją co najmniej $z$ dwa punkty.

W oryginalnym argumencie Becka C wynosi 100, a K jest nieokreśloną stałą; nie wiadomo, jakie są optymalne wartości C i K.

Dowód

Dowód twierdzenia Becka można podać w następujący sposób. Rozważmy zbiór P n punktów na płaszczyźnie. Niech j będzie dodatnią liczbą całkowitą. Powiedzmy, że para punktów A , B w zbiorze P jest j-spójna , jeśli linia łącząca A i B zawiera pomiędzy ${\ displaystyle 2 ^ {j}}$ i ${\ displaystyle 2 ^{j+1}-1}$ punktów P (w tym A i B ).

$n ^ {2}/2 ^ {3j} + n/2 ^ {j })} , w następujący$ jot n ( $zawierają$ Rozważ zbiór P n punktów i zbiór L wszystkich tych linii rozpiętych przez pary punktów P , które co najmniej punkty P . Ponieważ żadne dwa punkty nie mogą leżeć na dwóch różnych prostych ${\ Displaystyle | L | \ cdot {2 ^ {j} \ wybierz 2} \ równoważnik {n \ wybierz 2}}$ . Korzystając teraz z twierdzenia Szemerédi – Trottera , wynika, że ​​liczba przypadków między P i L wynosi co najwyżej ${\ Displaystyle O (n ^ {2}/2 ^ {2j} + n )}$ . Wszystkie linie łączące połączone j również leżą w L , a każda $nich$ ma co najmniej przypadki. Dlatego całkowita liczba takich linii wynosi ${\ Displaystyle O (n ^ {2}/2 ^ {3j} + n/2 ^ {j})}$ .

$2$ każda taka linia łączy ze sobą $\$ widzimy zatem, że co par punktów może być j -spójnych.

Niech C będzie dużą stałą. Sumując szereg geometryczny , widzimy , ${\ Displaystyle C \ równoważnik 2 ^ {j} \ równoważnik n/C}$ liczba par punktów, które są j -połączone dla pewnego j spełniającego , wynosi co najwyżej ${\ Displaystyle O (n ^ {2} / C)}$ .

Z drugiej strony, całkowita liczba par wynosi ${\ Displaystyle {\ Frac {n (n-1)} {2}}}$ . Tak więc $pary$ jeśli wybierzemy C jako wystarczająco duże, możemy znaleźć co najmniej na przykład), które nie są dla dowolnego $do {\ Displaystyle C \ równoważnik 2 ^ {j} \ równoważnik n / C$ . Linie łączące te pary albo przechodzą przez mniej niż 2 C , albo przechodzą przez więcej niż n / C punktów. Jeśli ten drugi przypadek zachodzi choćby dla jednej z tych par, to mamy pierwszy wniosek z twierdzenia Becka. $,$ że wszystkie pary są połączone liniami, które przechodzą przez punkty $linia$ co pary $istnieć$ co najmniej ${\ Displaystyle K = 4C (2C-1)}$ najmniej dwa punkty .