Теорема де Брейна — Ердеша
Теорема де Брейна — Ердеша — один з важливих результатів у геометрії інцидентності, встановлює точну нижню оцінку на число прямих, визначених точками на проєктивній площині. За двоїстістю з цієї теореми випливає обмеження на кількість перетинів конфігурації прямих.
Встановили Ніколас де Брейном і Пал Ердеш 1948 році.
Нехай дано набір з точок на проєктивній площині, з яких не всі лежать на одній прямій. Нехай це число всіх прямих, що проходять через пари точок з : Тоді . Більш того, якщо , то будь-які дві прямі перетинаються в точці з .
Стандартне доведення ведеться за індукцією. Теорема очевидно виконується для трьох точок, які не лежать на одній прямій. Нехай , твердження істинне для і — множина з точок, не всі з яких лежать на одній прямій. За теоремою Сильвестра одна з цих прямих проходить рівно через дві точки з . Позначимо ці дві точки і .
Якщо при видаленні точки решта точок будуть на одній прямій, то утворює майже пучок з прямих ( простих прямих проходять через , плюс одна пряма, що проходить через інші точки). В іншому випадку видалення утворює множину з неколінеарних точок. За припущенням індукції через проходять прямих, що щонайменше на одиницю менше від числа прямих, що проходять через точки множини .
- 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. — ISBN 0-521-59014-0.