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

Теорема де Брёйна — Эрдёша — один из важных результатов в геометрии инцидентности, устанавливает точную нижнюю оценку на число прямых, определённых [math]\displaystyle{ n }[/math] точками на проективной плоскости. По двойственности из этой теоремы следует ограничение на число пересечений конфигурации прямых.

История

Установлена Николасом де Брёйном и Палом Эрдёшем в 1948 году.

Формулировка

Пусть задан набор [math]\displaystyle{ P }[/math] из [math]\displaystyle{ n }[/math] точек на проективной плоскости, из которых не все лежат на одной прямой. Пусть [math]\displaystyle{ t }[/math] это число всех прямых, проходящих через пары точек из [math]\displaystyle{ P }[/math]: Тогда [math]\displaystyle{ t \geqslant n }[/math]. Более того, если [math]\displaystyle{ t=n }[/math], то любые две прямые пересекаются в точке из [math]\displaystyle{ P }[/math].

Доказательство

Стандартное доказательство ведётся по индукции. Теорема определённо верна для трёх точек, не лежащих на одной прямой. Пусть [math]\displaystyle{ n \gt 3 }[/math], утверждение верно для [math]\displaystyle{ n-1 }[/math] и [math]\displaystyle{ P }[/math] — множество из [math]\displaystyle{ n }[/math] точек, не все из которых лежат на одной прямой. По теореме Сильвестра одна из этих прямых проходит ровно через две точки из [math]\displaystyle{ P }[/math]. Обозначим эти две точки [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math].

Если при удалении точки [math]\displaystyle{ a }[/math] все оставшиеся точки будут на одной прямой, то [math]\displaystyle{ P }[/math] образует пучок из [math]\displaystyle{ P }[/math] прямых ([math]\displaystyle{ n-1 }[/math] простых прямых проходят через [math]\displaystyle{ P }[/math], плюс одна прямая, проходящая через остальные точки). В противном случае удаление [math]\displaystyle{ a }[/math] образует множество [math]\displaystyle{ P }[/math] из [math]\displaystyle{ n-1 }[/math] неколлинеарной точки. По предположению индукции через [math]\displaystyle{ P }[/math] проходят [math]\displaystyle{ n-1 }[/math] прямые, что по меньшей мере на единицу меньше числа прямых, проходящих через точки множества [math]\displaystyle{ P }[/math].

Литература

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.