Геометрия инцидентности

Геометрия инцидентности — раздел классической геометрии, изучающий структуры инцидентности, например принадлежность точки прямой.

В геометрии объекты, такие как евклидова плоскость, являются сложными объектами, использующими концепции длин, углов, непрерывности, отношения «лежит между» и инцидентности.

Структура инцидентности — это то, что остаётся, если отбросить все понятия, кроме данных о том, какие из изучаемых объектов (например, точки) лежат в других объектах (например, окружностях или прямых). Даже при таких ограничениях некоторые теоремы можно доказать и получить интересные факты относительно такой структуры. Такие фундаментальные результаты остаются верными, если добавить другие концепции для получения более богатой геометрии. Иногда авторы размывают различие между процессом изучения и объектом изучения, так что не удивительно, что некоторые авторы используют для структур инциденций название геометрии инциденций^[1].

Структуры инциденций возникают естественным образом и изучались в различных областях математики. Соответственно, существует отличающаяся терминология для описания таких объектов. В теории графов они называются гиперграфами, а в теории комбинаторных схем они называются блок-схемами. Кроме разницы в терминологии, в каждой области подход к изучению объекта отличается, и вопросы к объектам ставятся соответственно дисциплине. Если используется язык геометрии, как это делается в геометрии инциденций, говорят о фигурах. Возможно, однако, перевести результаты с терминологии одной дисциплины на язык другой, но часто это приводит к неуклюжим и запутанным утверждениям, не выглядящим естественным образом для дисциплины. В примерах, приведённых в статье, мы используем только примеры, имеющие геометрическое содержание.

Специальный случай, вызывающий большой интерес, имеет дело с конечным набором точек на евклидовой плоскости и в этом случае речь идёт о числе и типах прямых, которые эти точки определяют. Некоторые результаты этого случая можно распространить на более общие случаи, поскольку здесь рассматриваются только свойства инцидентности.

Структура инцидентности (P, L, I) состоит из множества P, элементы которого называются точками, множества L , элементы которого называются прямыми, и отношения инцидентности I между ними, то есть подмножества P × L, элементы которого называются флагами ^[2]. Если (A, l) — флаг, мы говорим, что A инцидентна l, или, что l инцидентна A (отношение симметрично), и пишем A I l. Интуитивно ясно, что точка и прямая находятся в таком отношении тогда и только тогда, когда точка лежит на прямой. Если дана точка B и прямая m, которые не образуют флаг, то точка не лежит на прямой и пара (B, m) называется антифлагом.

Нет естественного понятия расстояния (метрики) в структуре инциденций. Однако существует комбинаторная метрика в соответствующих графах инциденций (графах Леви), а именно, длина кратчайшего пути между двумя вершинами в этом двудольном графе. Расстояние между двумя объектами структуры инцидентности – двумя точками, двумя прямыми или точкой и прямой – может быть определено как расстояние между двумя соответствующими вершинами в графе инцидентности структуры инцидентности.

Другой путь определения расстояния опять использует понятия теории графов, на этот раз используется граф коллинеарности структуры инцидентности. Вершинами графа коллинеарности являются точки структуры инцидентности и две вершины соединены ребром, если существует прямая, инцидентная обоим точкам. Расстояние между двумя точками структуры инцидентности тогда можно определить как расстояние между ними в графе коллинеарности.

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

Наиболее изучаемые структуры инциденций, это структуры, удовлетворяющие некоторым дополнительным свойствам (аксиомам), такие как проективные плоскости, аффинные плоскости^[англ.]*, обобщённые многоугольники, частичные геометрии и почти многоугольники. Весьма общие структуры инциденций могут быть получены наложением «мягких» условий, таких как:

Частично линейное пространство^[англ.] является структурой инциденций, для которой выполняются следующие аксиомы^[3]:

• Любая пара различных точек определяет максимум одну прямую.
• Любая прямая содержит по меньшей мере две различные точки.

В частично линейном пространстве также верно, что любая пара различных прямых пересекаются максимум в одной точке. Это утверждение не включается в аксиомы, поскольку легко доказывается из первой аксиомы.

Дальнейшие ограничения задаются условиями регулярности:

RLk: Каждая прямая инцидентна одному и тому же числу точек. Если это число конечно, оно часто обозначается как k.

RPr: Каждая точка инцидентна одному и тому же числу прямых. Если это число конечно, его часто обозначают как r.

Из второй аксиомы частично линейного пространства следует, что k > 1. Ни одно из условий регулярности не вытекает из другого, так что следует принять r > 1.

Конечное частично линейное пространство, удовлетворяющее обоим условиям регулярности с k, r > 1, называется тактической конфигурацией^[4]. Некоторые авторы называют такие конфигурации просто конфигурациями^[5] или проективными конфигурациями^[6]. Если тактическая конфигурация имеет n точек и m прямых, то, после двойного подсчёта флагов, получается соотношение nr = mk. Обычно используется обозначение (n_r, m_k)-конфигурация. В специальном случае, когда n = m (а потому, r = k), вместо обозначения (n_k, n_k) часто пишут просто (n_k).

Линейное пространство является частично линейным пространством, таким, что^[3]:

• Любая пара различных точек определяет в точности одну прямую.

Некоторые авторы добавляют аксиому «невырожденности» (или «нетривиальности») к определению (частичного) линейного пространства, такую как:

• Существуют по меньшей мере две различные прямые^[7].

Аксиома невырожденности позволяет исключить некоторые очень маленькие примеры (в основном те, в которых множества P или L состоят менее чем из двух элементов), которые были бы исключениями в общих утверждениях о структурах инцидентности. Альтернативный подход — считать структуры инцидентности, не удовлетворяющие аксиоме невырожденности тривиальными, а удовлетворяющие — нетривиальными.

Любое нетривиальное линейное пространство содержит по меньшей мере три точки и три прямые, так что простейшее нетривиальное линейное пространство — треугольник.

Линейное пространство, имеющее по меньшей мере три точки на каждой прямой, является конфигурацией Сильвестера – Галлаи.

Некоторые из базовых понятий и терминологии возникают из геометрических примеров, особенно из проективных плоскостей и аффинных плоскостей^[англ.]*.

Проективная плоскость — это линейное пространство, в котором:

• Любая пара различных прямых пересекаются в точности в одной точке
• Выполняется условие невырожденности — существует четыре точки, никакие три из которых не коллинеарны.

На проективных плоскостях существует биекция между P и L. Если P является конечным множеством, о проективной плоскости говорят как о конечной проективной плоскости. Порядок конечной проективной плоскости равен n = k – 1, то есть на единицу меньше числа точек на прямой. Все известные проективные плоскости имеют порядки, равные степени простого числа. Проективная плоскость порядка n является конфигурацией ((n² + n + 1)_{n + 1}).

Наименьшая проективная плоскость имеет порядок два и известна как плоскость Фано.

Эта знаменитая геометрия инциденций была разработана итальянским математиком Джино Фано. В его работе^[8] по доказательству независимости множества аксиом для проективного n-пространства, которую он разрабатывал ^[9], он создал конечное трёхмерное пространство с 15 точками, 35 прямыми и 15 плоскостями, в котором каждая прямая содержит только три точки ^[10]. Плоскости в этом пространстве состоят из семи точек и семи прямых, которые известны как плоскости Фано.

Плоскость Фано не может быть представлена на евклидовой плоскости с использованием только точек и отрезков (т.е. нереализуема). Это следует из теоремы Сильвестра.

Полный четырёхугольник состоит из четырёх точек, никакие три из которых не коллинеарны. На плоскости Фано три точки, не принадлежащие полному четырёхугольнику, являются диагональными точками четырёхугольника и коллинеарны. Это противоречит аксиоме Фано, часто используемой в аксиоматизации евклидовой плоскости, которая утверждает, что три диагональные точки полного четырёхугольника никогда не коллинеарны.

Аффинная плоскость — это линейное пространство, удовлетворяющее:

• Для любой точки A и прямой l, не инцидентной точке (антифлаг), существует в точности одна прямая m, инцидентная A (то есть A I m), не пересекающая l (аксиома Плейфера)
• Выполняется условие невырожденности — существует треугольник, т.е. три неколлинеарные точки.

О прямых l и m в утверждении аксиомы Плейфера говорят как о параллельных. Любая аффинная плоскость может быть единственным образом расширена до проективной плоскости. Порядок конечной аффинной плоскости равен k, числу точек на прямой. Аффинная плоскость порядка n является конфигурацией ((n²)_{n + 1}, (n² + n)_n).

Аффинная плоскость порядка три является конфигурацией (9₄, 12₃). Если конфигурация вложена в некоторое объемлющее пространство, её называют конфигурацией Гессе. Конфигурация нереализуема на евклидовой плоскости, но реализуема на комплексной проективной плоскости как девять точек перегиба эллиптической кривой с 12 прямыми, инцидентными тройкам этих точек перегиба.

12 прямых могут быть разбиты на четыре класса, внутри которых прямые попарно не пересекаются. Эти классы называются классами параллельности прямых. Если добавить ещё четыре новые точки, по одной точке в каждый класс параллельности, и считать, что все прямые класса параллельности пересекаются в этой новой точке (таким образом, теперь все прямые теперь пересекаются), и добавить ещё одну прямую, содержащую все четыре новые точки, получим проективную плоскость порядка три, конфигурацию (13₄). В обратную сторону, начав с проективной плоскости порядка три (такая плоскость единственна) и удалив любую (одну) прямую и все лежащие на ней точки, получим аффинную плоскость порядка три (она тоже единственна).

Удаление одной точки и четырёх прямых, проходящих через неё (но не другие точки на этой прямой), получим конфигурацию (8₃) Мёбиуса — Кантора.

Если задано целое число α ≥ 1, тактическая конфигурация, удовлетворяющая аксиоме:

• Для любого антифлага (B, m) существуют α флагов (A, l), такие что B I l и A I m,

называется частичной геометрией. Если существует s + 1 точек на прямой и t + 1 прямых проходят через точку, обозначение этой частичной геометрии — pg(s, t, α).

Если α = 1, эти частичные геометрии являются обобщёнными четырёхугольниками.

Если α = s + 1, конфигурации называются системами Штейнера.

Для n > 2 ^[11], обобщённый n-угольник — это частично линейное пространство, граф инцидентности которого Γ имеет свойство:

• Обхват графа Γ (длина кратчайшего цикла) является удвоенным диаметром графа Γ (наибольшее расстояние между двумя вершинами, n в нашем случае).

Обобщённый 2-угольник — это структура инцидентности, которая не является частично линейным пространством, состоящая по меньшей мере из двух точек и двух прямых, в которой каждая точка инцидентна каждой прямой. Графом инцидентности обобщённого 2-угольника является полный двудольный граф.

Обобщённый n-угольник не содержит никаких простых m-угольников для 2 ≤ m < n и для каждой пары объектов (две точки, две прямые или точка с прямой) существует обычный n-угольник, содержащий оба объекта.

Обобщённые 3-угольники являются проективными плоскостями. Обобщённые 4-угольники называются обобщёнными четырёхугольниками. По теореме Фейта-Хигмана существует только конечное число обобщённых n-угольников по меньшей мере с тремя точками на каждой прямой и тремя прямыми, проходящими через каждую прямую, и число n равно 2, 3, 4, 6 или 8.

Для неотрицательных целых d почти 2d-угольник — это структура инцидентности, такая, что:

• Максимальное расстояние (измеряется по графу коллинеарности) между двумя точками равно d
• Для любой точки X и прямой l существует единственная точка на l, ближайшая к X.

Почти 0-угольник — это точка, а почти 2-угольник — прямая. Граф коллинеарности почти 2-угольника — полный граф. Почти 4-угольник — это обобщённый четырёхугольник (возможно, вырожденный). Любой конечный обобщённый многоугольник, за исключением проективных плоскостей, является тесным многоугольником. Любой связный двудольный граф является почти многоугольником и любой почти многоугольник, имеющий в точности две точки на каждой прямой, является связным двудольным графом. Также все двойственные полярные пространства^[англ.] являются почти многоугольниками.

Многие почти многоугольники связаны с конечными простыми группами^[англ.], подобными группам Матьё и группа Янко J2. Более того, обобщённые 2d-угольники, связанные с группами лиева типа, являются специальными случаями почти 2d-угольников.

Абстрактная плоскость Мёбиуса (или инверсная плоскость) — это структура инцидентности, в которой, во избежание возможной путаницы с терминологией классического случая, прямые называют циклами или блоками.

Конкретно: плоскость Мёбиуса — это структура инцидентности точек и циклов, такая, что:

• Любая тройка различных точек инцидентна в точности одному циклу.
• Для любого флага (P, z) и любой точки t Q, не инцидентной z, существует единственный цикл z^∗ с P I z^∗, Q I z^∗ и z ∩ z^∗ = {P}. (Говорят, что циклы касаются P.)
• Любой цикл имеет по меньшей мере три точки и существует по меньшей мере один цикл.

Структура инцидентности, полученная из любой точки P плоскости Мёбиуса путём выбора в качестве точек всех точек, отличных от P, а в качестве прямых выбора только тех циклов, которые содержат P (с удалённой P), является аффинной плоскостью. Эта структура называется остатком P в теории схем.

Конечная плоскость Мёбиуса порядка m — это тактическая конфигурация с k = m + 1 точками в каждом цикле, которая является 3-дизайном, блок-схемой 3-(m² + 1, m + 1, 1).

Вопрос, поставленный Д.Д. Сильвестером в 1893 и, наконец, доказанной Тибором Галлаи^[англ.], касается инцидентности конечного числа точек в евклидовой плоскости.

Теорема (Сильвестр — Галлаи): Точки конечного множества точек на евклидовой плоскости либо коллинеарны, либо существует прямая, инцидентная в точности двум точкам.

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

Связанный результат — теорема де Брёйна — Эрдёша. Николас де Брёйн и Пал Эрдёш доказали результат в более общих условиях проективной плоскости, но результат остаётся верным на евклидовой плоскости. Теорема гласит:^[12]

На проективной плоскости любое множество n неколлинеарных точек определяет по меньшей мере n различных прямых.

Как указали авторы, поскольку их доказательство было комбинаторным, результат выполняется в более сильных условиях, фактически в любой геометрии инцидентности. Они также упомянули, что версия для евклидовой плоскости может быть доказана из теоремы Сильвестера — Галлаи с помощью индукции.

Граница числа флагов, определённая конечным множеством точек и прямых, задаётся теоремой:

Теорема (Семереди – Троттер): Если задано n точек и m прямых на плоскости, число флагов (пар инцидентности точка-прямая) равно:

${\displaystyle O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),}$

И эта граница не может быть улучшена.

Этот результат можно использовать для доказательства теоремы Бека.

Теорема Бека утверждает, что конечные наборы точек на плоскости распадаются на два крайних случая — в одних наборах все точки лежат на одной прямой, а в других нужно большое число прямых для соединения всех точек.

Теорема утверждает, что существуют положительные константы C, K, такие, что, если заданы n точек на плоскости, по меньшей мере одно из следующих утверждение верно:

1. Существует прямая, содержащая по меньшей мере n/C точек.
2. Существует по меньшей мере n²/K прямых, каждая из которых содержит по меньшей мере две точки.

В исходных доказательствах Бека C равно 100, а K является неопределённой константой. Оптимальные значения C и K неизвестны.

• Проективные геометрии
• Многоугольник Моуфанга^[англ.]
• Двойная шестёрка Шлефли
• Конфигурация Рейе
• Конфигурация Кремоны — Ричмонда
• Конфигурация Куммера^[англ.]
• Конфигурация Клейна
• Недезарговы плоскости

• Комбинаторные схемы
• Конечная геометрия
• Теорема о пересечениях^[англ.]
• Граф Леви

• G. Fano. Sui postulati fondamentali della geometria proiettiva // Giornale di Matematiche. — 1892. — Т. 30. — С. 106–132.
• H. S. M. Coxeter. Introduction to Geometry. — New York: John Wiley & Sons, 1969. — С. 233. — ISBN 0-471-50458-0.
• David Hilbert, Stephan Cohn-Vossen. Geometry and the Imagination. — 2nd. — Chelsea, 1952. — С. 94–170. — ISBN 0-8284-1087-9.
• Lynn Margaret Batten. Combinatorics of Finite Geometries. — New York: Cambridge University Press, 1986. — ISBN 0-521-31857-2.
• Lynn Margaret Batten, Albrecht Beutelspacher. The Theory of Finite Linear Spaces. — New York: Cambridge University Press, 1993. — ISBN 0-521-33317-2.
• Buekenhout, Francis (1995), Handbook of Incidence Geometry: Buildings and Foundations, Elsevier B.V.
• Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton: Chapman & Hall/ CRC, 2007. — ISBN 1-58488-506-8.
• Collino, Alberto; Conte, Alberto; Verra, Alessandro (2013). "On the life and scientific work of Gino Fano". arXiv:1311.7177.
• Peter Dembowski. Finite geometries. — Berlin, New York: Springer-Verlag, 1968. — Т. 44. — (Ergebnisse der Mathematik und ihrer Grenzgebiete). — ISBN 3-540-61786-8.
• Malkevitch, Joe Finite Geometries?  (неопр.) Дата обращения: 2 декабря 2013.
• Moorhouse, G. Eric Incidence Geometry. MATH 5700 Fall 2007 (англ.) (pdf). University of Wyoming (август 2007). Дата обращения: 17 января 2017. Архивировано из оригинала 29 октября 2013 года.
• Johannes Ueberberg. Foundations of Incidence Geometry. — Springer, 2011. — (Springer Monographs in Mathematics). — ISBN 978-3-642-26960-8. — doi:10.1007/978-3-642-20972-7..
• Ernest E. Shult. Points and Lines. — Springer, 2011. — (Universitext). — ISBN 978-3-642-15626-7. — doi:10.1007/978-3-642-15627-4..

• Simeon Ball. Finite Geometry and Combinatorial Applications. — Cambridge University Press, 2015. — (London Mathematical Society Student Texts). — ISBN 978-1107518438..

• incidence system на сайте Математическая энциклопедия