Теорема Де Брейна – Эрдеша (геометрия инцидентности) - De Bruijn–Erdős theorem (incidence geometry)

Эта статья о количестве линий, определяемых конечным набором точек. О раскраске бесконечных графов см. Теорема Де Брейна – Эрдеша (теория графов).

В геометрия падения, то Теорема Де Брейна – Эрдеша., первоначально опубликовано Николаас Говерт де Брёйн и Пол Эрдёш  (1948 ), утверждает нижняя граница по количеству строк, определяемых п очков в проективная плоскость. От двойственность, это также ограничение на количество точек пересечения, определяемое конфигурацией линий.

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

Формулировка теоремы

Почти карандаш по семи точкам

Позволять п быть конфигурацией п точки на проективной плоскости, а не все на прямой. Позволять т быть количеством строк, определяемымп. Потом,

  • т ≥ п, и
  • если т = п, любые две линии имеют ровно одну точку п в общем. В таком случае, п является либо проективной плоскостью, либо п это возле карандаша, что означает, что именно п - 1 из баллов коллинеарен.

Евклидово доказательство

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

Предполагать п > 3 и теорема верна для п - 1.Пусть п быть набором п указывает, что не все коллинеарны. Теорема Сильвестра – Галлаи утверждает, что есть линия, содержащая ровно две точки п. Такие две точечные линии называются обычные линии.Позволять а и б быть двумя точками п по обычной линии.

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

В противном случае удаление а производит набор, П' , из п - 1 балл, не все коллинеарны. По предположению индукции П' определяет по крайней мере п - 1 линия. Обычная линия, определяемая а и б не входит в их число, поэтому п определяет по крайней мере п линий.

Доказательство Дж. Х. Конвея

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

использованная литература

  1. ^ Стасис Юкна, Экстремальная комбинаторика, Второе издание, Springer Verlag, 2011 г., страницы 167 - 168.

Источники

  • де Брёйн, Н.Г.; Эрдеш, П. (1948), «О комбинаторной [sic] проблеме» (PDF), Indagationes Mathematicae, 10: 421–423.
  • Баттен, Линн Маргарет (1997), "2.2 Теорема де Брейна – Эрдеша", Комбинаторика конечных геометрий (2-е изд.), Cambridge University Press, стр. 25–27, ISBN  0-521-59014-0