Теорема Бека (геометрія)

1. Затвердження теореми [ правити | правити код ]
2. Доведення [ правити | правити код ]
3. Затвердження теореми [ правити | правити код ]
4. Доведення [ правити | правити код ]

Про теорему Бека в теорії категорій (однофамілець) див. Статтю Теорема Бека про монадізіруемості [en]

Теорема Бека - це один з декількох результатів комбінаторної геометрії , Два з яких наведені нижче. Обидві теореми з'явилися разом з деякими іншими важливими теоремами в добре відомій статті Джозефа Бека [1] . Два результату, описані нижче стосуються нижніх меж числа прямих, визначених безліччю точок на площині. (Кажуть, що будь-яка пряма, що з'єднує щонайменше дві точки безлічі, визначається точковим безліччю.)

Теорема Ердеша - Бека - це варіант класичного результату Л.М. Келлі і У.О.Дж. Мозера [2] про зміни n точок, з яких не більше n - k колінеарні для деякого числа 0 <k <O (√ n). Вони показали, що якщо n досить велике щодо k, то конфігурація містить щонайменше kn - (1/2) (3 k + 2) (k - 1) прямих [3] .

Елекеш і Чаба Тоз помітили, що теорема Ердеша - Бека не поширюється легко на більш високі розмірності [4] . Візьмемо, для прикладу, безліч з 2 n точок в R 3, що лежать на двох перехресних прямих . Припустимо, що кожна з цих двох прямих инцидентна n точкам. Така конфігурація охоплює лише 2 n площин. Таким чином, тривіального розширення гіпотези на безлічі точок в R d недостатньо для отримання потрібного результату.

Результат вперше висловив в якості гіпотези Ердеш , Довів теорему Бек [5] .

Затвердження теореми [ правити | правити код ]

Нехай S - безліч з n точок на площині. Якщо ніякі з більш ніж nk точок не лежать на одній прямій для деякого 0 ≤ k <n - 2, то існує Ω (nk) прямих, що задаються точками з S.

Доведення [ правити | правити код ]

Теорема Бека стверджує, що кінцевий набір точок на площині потрапляє в один з двох екстремальних випадків. В одному випадку велика частка точок лежить на одній прямій, в іншому випадку потрібна велика кількість прямих, щоб з'єднати всі крапки.

Хоча в статті це не вказується, цей результат випливає з теореми Ердеша - Бека [6]

Затвердження теореми [ правити | правити код ]

Теорема стверджує, що існують дві позитивні константи C і K, такі, що для будь-якого числа n точок на площині вірно одне з наступних тверджень:

1. Існує пряма, яка містить щонайменше n / C точок.
2. Існує щонайменше n 2 / K {\ displaystyle n ^ {2} / K} прямих, кожна з яких містить щонайменше дві точки.

В оригінальній статті Бека величина C дорівнює 100, а величина константи K не вказана. Оптимальні значення C і K невідомі.

Доведення [ правити | правити код ]

Довести теорему Бека можна наступним чином. Нехай P - безліч з n точок на площині. Нехай j - позитивне ціле число. Скажімо, що пара точок A і B в безлічі P j-зв'язні, якщо пряма, що з'єднує A і B містить від 2 j {\ displaystyle 2 ^ {j}} до 2 j + 1 - 1 {\ displaystyle 2 ^ {j + 1} -1} точок безлічі P (включаючи A і B).

з теореми Семереді - Троттера випливає, що число таких прямих одно O (n 2/2 3 j + n / 2 j) {\ displaystyle O (n ^ {2} / 2 ^ {3j} + n / 2 ^ {j})} з наступних причин. Нехай безліч P складається з n точок і безліч L всіх таких прямих, що з'єднують пари точок безлічі P, які містять щонайменше 2 j {\ displaystyle 2 ^ {j}} точок безлічі P. Зауважимо, що | L | ⋅ (2 j 2) ≤ (n 2) {\ displaystyle | L | \ cdot {2 ^ {j} \ choose 2} \ leq {n \ choose 2}} , Оскільки ніякі дві точки не можуть лежати на двох різних прямих. тепер використовуємо теорему Семереді - Троттера , З якої випливає, що число інціденцій між P і L не перевищує O (n 2/2 2 j + n) {\ displaystyle O (n ^ {2} / 2 ^ {2j} + n)} . Всі прямі, що з'єднують j-зв'язкові точки, також знаходяться в L, і кожна пряма має щонайменше 2 j {\ displaystyle 2 ^ {j}} інціденцій. Таким чином, загальне число таких прямих одно O (n 2/2 3 j + n / 2 j) {\ displaystyle O (n ^ {2} / 2 ^ {3j} + n / 2 ^ {j})} .

Оскільки кожна така пряма з'єднує Ω (2 2 j) {\ displaystyle \ Omega (2 ^ {2j})} пар точок, ми бачимо, що не більше O (n 2/2 j + 2 j n) {\ displaystyle O (n ^ {2} / 2 ^ {j} + 2 ^ {j} n)} пар точок може бути j -связни.

Тепер, нехай C - досить велика константа. Підсумовуючи геометричну прогресію , Ми отримуємо, що число j -связних пар точок для деякого j, що задовольняють нерівності C ≤ 2 j ≤ n / C {\ displaystyle C \ leq 2 ^ {j} \ leq n / C} , Не перевищує O (n 2 / b C) {\ displaystyle O (n ^ {2} / b \ C)} .

З іншого боку, загальне число пар точок одно n (n - 1) 2 {\ displaystyle {\ frac {n (n-1)} {2}}} . Тоді, якщо ми виберемо C досить великим, ми можемо знайти щонайменше n 2/4 {\ displaystyle n ^ {2} / 4} пар (наприклад), що не j -связни для будь-якого C ≤ 2 j ≤ n / C {\ displaystyle C \ leq 2 ^ {j} \ leq n / C} . Прямі, що з'єднують ці точки, проходячи через менш ніж 2 C точок або більше ніж n / C точок. Якщо останнє твердження виконується для хоча б для однієї пари, виконується перше твердження теореми Бека. Тоді ми можемо припустити, що все n 2/4 {\ displaystyle n ^ {2} / 4} пар з'єднані прямими, які проходять через менш ніж 2 C точок. Однак така пряма може з'єднувати не більше C (2 C - 1) {\ displaystyle C (2C-1)} пар точок. Тоді має бути щонайменше n 2/4 C (2 C - 1) {\ displaystyle n ^ {2} / 4C (2C-1)} прямих, що з'єднують щонайменше дві точки, так що твердження теореми виходить, якщо прийняти K = 4 C (2 C - 1) {\ displaystyle K = 4C (2C-1)} .

1. ↑ Beck, 1983 , С. 281-297.
2. ↑ William OJ Moser (неопр.).
3. ↑ Kelly, Moser, 1958 , С. 210-219.
4. ↑ Elekes, Tóth, 2005 , С. 16-21.
5. ↑ Beck, 1983 , С. 281-297 Theorem 5.2.
6. ↑ Теорема Бека виходить, якщо покласти k = n (1 - 1 / C) і застосувати теорему Ердеша - Бека.

Beck J. On the lattice property of the plane and some problems of Dirac , Motzkin, and Erdős in combinatorial geometry // Combinatorica. - 1983. - Т. 3. - С. 281-297. - DOI : 10.1007 / BF02579184 .