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

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

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

Історія

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

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

Нехай дано набір $P$ з $n$ точок на проєктивній площині, з яких не всі лежать на одній прямій. Нехай $t$ це число всіх прямих, що проходять через пари точок з $P$: Тоді $t⩾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$.

Див. також

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

Література

• Шаблон:Стаття
• Шаблон:Книга