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

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

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

Історія

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

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

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

Доведення

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

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

Див. також

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

Література

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