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

Теорема де Брёйна — Эрдёша — один из важных результатов в геометрии инцидентности, устанавливает точную нижнюю оценку на число прямых, определённых $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. — С. 421—423.
Lynn Margaret Batten. Combinatorics of finite geometries. — Cambridge University Press, 1997. — С. 25–27. — ISBN 0-521-59014-0.