Теорема де Брейна – Эрдеша (геометрия инцидентности)

В геометрии инцидентности теорема Де Брейна–Эрдёша , первоначально опубликованная Николаасом Говертом де Брейном и Полом Эрдёшем в 1948 году, ^[1] устанавливает нижнюю границу числа прямых, определяемых n точками в проективной плоскости . По двойственности это также является границей числа точек пересечения, определяемых конфигурацией прямых. ^[2]

Хотя доказательство, данное Де Брейном и Эрдёшем, является комбинаторным , Де Брейн и Эрдёш отметили в своей статье, что аналогичный ( евклидов ) результат является следствием теоремы Сильвестра–Галлаи , полученным индукцией по числу точек. ^[1]

Пусть P — конфигурация из n точек в проективной плоскости, не все из которых находятся на одной прямой. Пусть t — число прямых, определяемых  P. Тогда,

• т ≥ n , и
• если t = n , любые две прямые имеют ровно одну общую точку P. В этом случае P является либо проективной плоскостью, либо P является почти пучком , что означает, что ровно n - 1 точек лежат на одной прямой . ^[2]

Теорема, очевидно, верна для трех неколлинеарных точек. Действуем по индукции .

Предположим, что n  > 3, и теорема верна для n  − 1. Пусть P — множество из n точек, не все из которых лежат на одной прямой. Теорема Сильвестра–Галлаи утверждает, что существует прямая, содержащая ровно две точки P. Такие двухточечные прямые называются обычными прямыми . Пусть a и b — две точки P на обычной прямой.

Если удаление точки a приводит к созданию набора коллинеарных точек, то P порождает почти пучок из n прямых ( n - 1 обычных прямых, проходящих через a, плюс одна прямая, содержащая другие n - 1 точек).

В противном случае удаление a создает набор P' из n  − 1 точек, которые не все коллинеарны. По индукционной гипотезе P' определяет по крайней мере n  − 1 прямых. Обычная прямая, определяемая a и b , не входит в их число, поэтому P определяет по крайней мере n прямых.

У Джона Хортона Конвея есть чисто комбинаторное доказательство, которое, следовательно, справедливо также для точек и линий над комплексными числами , кватернионами и октонионами . ^[3]