Теорема де Брейна — Ердеша

Теорема де Брейна — Ердеша — один з важливих результатів у геометрії інцидентності, встановлює точну нижню оцінку на число прямих, визначених ${\displaystyle n}$ точками на проєктивній площині. За з цієї теореми випливає обмеження на кількість перетинів конфігурації прямих.

(Майже пучок) на семи точках

Історія

Встановили Ніколас де Брейном і Пал Ердеш .

Формулювання

Нехай дано набір ${\displaystyle P}$ з ${\displaystyle n}$ точок на проєктивній площині, з яких не всі лежать на одній прямій. Нехай ${\displaystyle t}$ це число всіх прямих, що проходять через пари точок з ${\displaystyle P}$: Тоді ${\displaystyle t\geqslant n}$. Більш того, якщо ${\displaystyle t=n}$, то будь-які дві прямі перетинаються в точці з ${\displaystyle P}$.

Доведення

Стандартне доведення ведеться за індукцією. Теорема очевидно виконується для трьох точок, які не лежать на одній прямій. Нехай ${\displaystyle n>3}$, твердження істинне для ${\displaystyle n-1}$ і ${\displaystyle P}$ — множина з ${\displaystyle n}$ точок, не всі з яких лежать на одній прямій. За теоремою Сильвестра одна з цих прямих проходить рівно через дві точки з ${\displaystyle P}$. Позначимо ці дві точки ${\displaystyle a}$ і ${\displaystyle b}$.

Якщо при видаленні точки ${\displaystyle a}$ решта точок будуть на одній прямій, то ${\displaystyle P}$ утворює (майже пучок) з ${\displaystyle P}$ прямих (${\displaystyle n-1}$ простих прямих проходять через ${\displaystyle P}$, плюс одна пряма, що проходить через інші точки). В іншому випадку видалення ${\displaystyle a}$ утворює множину ${\displaystyle P}$ з ${\displaystyle n-1}$ неколінеарних точок. За припущенням індукції через ${\displaystyle P}$ проходять ${\displaystyle n-1}$ прямих, що щонайменше на одиницю менше від числа прямих, що проходять через точки множини ${\displaystyle P}$.

Див. також

• Нерівність Фішера

Література

• N. G. de Bruijn, P. Erdős. A combinatioral [sic] problem // Indagationes Mathematicae. — 1948. — Т. 10 (16 червня). — С. 421—423. з джерела 28 червня 2021. Процитовано 26 червня 2021.
• Lynn Margaret Batten. Combinatorics of finite geometries. — Cambridge University Press, 1997. — С. 25–27. — .