В математике геометрия инцидентности — это изучение структур инцидентности . Геометрическая структура , такая как евклидова плоскость, является сложным объектом, который включает в себя такие концепции, как длина, углы, непрерывность, промежуточность и инцидентность . Структура инцидентности — это то, что получается, когда все другие концепции удаляются, и все, что остается, — это данные о том, какие точки лежат на каких линиях. Даже при таком строгом ограничении теоремы могут быть доказаны, и появляются интересные факты, касающиеся этой структуры. Такие фундаментальные результаты остаются в силе, когда добавляются дополнительные концепции для формирования более богатой геометрии. Иногда случается, что авторы стирают различие между исследованием и объектами этого исследования, поэтому неудивительно, что некоторые авторы называют структуры инцидентности геометриями инцидентности. [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 ) .
Линейное пространство — это частичное линейное пространство, такое что: [7]
Некоторые авторы добавляют аксиому «невырожденности» (или «нетривиальности») к определению (частичного) линейного пространства, например:
Это используется для исключения некоторых очень маленьких примеров (в основном, когда множества P или L имеют менее двух элементов), которые обычно являются исключениями из общих утверждений, сделанных относительно структур инцидентности. Альтернативой добавлению аксиомы является обозначение структур инцидентности, которые не удовлетворяют аксиоме, как тривиальных , а те, которые удовлетворяют, как нетривиальные .
Каждое нетривиальное линейное пространство содержит по крайней мере три точки и три прямые, поэтому простейшим нетривиальным линейным пространством, которое может существовать, является треугольник.
Линейное пространство, имеющее по крайней мере три точки на каждой линии, является схемой Сильвестра–Галлаи .
Некоторые из основных понятий и терминов возникают из геометрических примеров, в частности, проективных плоскостей и аффинных плоскостей .
Проективная плоскость — это линейное пространство, в котором:
и удовлетворяет условию невырожденности:
Между P и L в проективной плоскости существует биекция . Если P — конечное множество, проективная плоскость называется конечной проективной плоскостью. Порядок конечной проективной плоскости равен n = k – 1 , то есть на единицу меньше числа точек на прямой. Все известные проективные плоскости имеют порядки, являющиеся степенями простых чисел . Проективная плоскость порядка n — это конфигурация (( n 2 + n + 1) n + 1 ) .
Наименьшая проективная плоскость имеет порядок два и известна как плоскость Фано .
Эта знаменитая геометрия инцидентности была разработана итальянским математиком Джино Фано . В своей работе [9] по доказательству независимости множества аксиом для проективного n -пространства , которое он разработал, [10] он создал конечное трехмерное пространство с 15 точками, 35 прямыми и 15 плоскостями, в котором каждая прямая имела только три точки на себе. [11] Плоскости в этом пространстве состояли из семи точек и семи прямых и теперь известны как плоскости Фано .
Плоскость Фано не может быть представлена в евклидовой плоскости с использованием только точек и отрезков прямых (т. е. она нереализуема). Это следствие теоремы Сильвестра–Галлаи , согласно которой каждая реализуемая геометрия инцидентности должна включать обычную прямую , прямую, содержащую только две точки. Плоскость Фано не имеет такой прямой (т. е. она является конфигурацией Сильвестра–Галлаи ), поэтому она нереализуема. [12]
Полный четырехугольник состоит из четырех точек, никакие три из которых не лежат на одной прямой. В плоскости Фано три точки, не лежащие на полном четырехугольнике, являются диагональными точками этого четырехугольника и лежат на одной прямой. Это противоречит аксиоме Фано , часто используемой в качестве аксиомы для евклидовой плоскости, которая гласит, что три диагональные точки полного четырехугольника никогда не лежат на одной прямой.
Аффинная плоскость — это линейное пространство, удовлетворяющее:
и удовлетворяющие условию невырожденности:
Прямые l и m в формулировке аксиомы Плейфера называются параллельными . Каждая аффинная плоскость может быть единственным образом расширена до проективной плоскости. Порядок конечной аффинной плоскости равен k , числу точек на прямой. Аффинная плоскость порядка n — это конфигурация (( n 2 ) n + 1 , ( n 2 + n ) n ) .
Аффинная плоскость порядка три — это конфигурация (9 4 , 12 3 ) . При вложении в некоторое окружающее пространство она называется конфигурацией Гессе . Она не реализуема в евклидовой плоскости, но реализуема в комплексной проективной плоскости как девять точек перегиба эллиптической кривой с 12 прямыми, инцидентными тройкам этих кривых.
12 прямых можно разбить на четыре класса по три прямые в каждом, где в каждом классе прямые взаимно не пересекаются. Эти классы называются параллельными классами прямых. Добавление четырех новых точек, каждая из которых добавляется ко всем прямым одного параллельного класса (так что все эти прямые теперь пересекаются), и одной новой прямой, содержащей только эти четыре новые точки, дает проективную плоскость третьего порядка, конфигурацию (13 4 ) . И наоборот, начиная с проективной плоскости третьего порядка (она уникальна) и удаляя любую отдельную прямую и все точки на этой прямой, получаем эту аффинную плоскость третьего порядка (она также уникальна).
Удаление одной точки и четырех прямых, проходящих через эту точку (но не других точек на них), дает конфигурацию (8 3 ) Мёбиуса–Кантора .
,_the_Doily.svg/1280px-GQ(2,2),_the_Doily.svg.png)
При заданном целом числе α ≥ 1 тактическая конфигурация удовлетворяет:
называется частичной геометрией . Если на прямой лежит s + 1 точка, а через точку проходит t + 1 прямых, то обозначение частичной геометрии — pg( s , t , α ) .
Если α = 1, то эти частичные геометрии являются обобщенными четырехугольниками .
Если α = s + 1, то они называются системами Штейнера .
При n > 2 [ 13] обобщенный n -угольник — это частичное линейное пространство, граф инцидентности Γ которого обладает свойством :
Обобщенный 2-угольник — это структура инцидентности, которая не является частичным линейным пространством, состоящая по крайней мере из двух точек и двух прямых, при этом каждая точка инцидентна каждой прямой. Граф инцидентности обобщенного 2-угольника — это полный двудольный граф.
Обобщенный n -угольник не содержит обычного m -угольника при 2 ≤ m < n, и для каждой пары объектов (две точки, две прямые или точка и прямая) существует обычный n -угольник, содержащий их оба.
Обобщенные 3-угольники являются проективными плоскостями. Обобщенные 4-угольники называются обобщенными четырехугольниками . По теореме Фейта-Хигмана единственные конечные обобщенные n -угольники с по крайней мере тремя точками на прямую и тремя прямыми на точку имеют n = 2, 3, 4, 6 или 8.
Для неотрицательного целого числа d близкий к 2 d -угольник является структурой инцидентности такой, что:
Почти 0-угольник — это точка, а почти 2-угольник — это линия. Граф коллинеарности почти 2-угольника — это полный граф . Почти 4-угольник — это обобщенный четырехугольник (возможно, вырожденный). Каждый конечный обобщенный многоугольник, за исключением проективных плоскостей, является близким многоугольником. Любой связный двудольный граф является близким многоугольником, а любой близкий многоугольник с ровно двумя точками на линии является связанным двудольным графом. Кроме того, все двойственные полярные пространства являются близкими многоугольниками.
Многие почти многоугольники связаны с конечными простыми группами, такими как группы Матье и группа Янко J2 . Более того, обобщенные 2 d -угольники, связанные с группами типа Ли , являются частными случаями почти 2 d -угольников.
Абстрактная плоскость Мёбиуса (или инверсная плоскость) представляет собой структуру инцидентности, в которой, чтобы избежать возможной путаницы с терминологией классического случая, линии называются циклами или блоками .
В частности, плоскость Мёбиуса представляет собой структуру инцидентности точек и циклов, такую что:
Структура инцидентности, полученная в любой точке P плоскости Мёбиуса, если взять в качестве точек все точки, отличные от P , а в качестве линий — только те циклы, которые содержат P (с удаленной точкой P ), является аффинной плоскостью. Эта структура называется остаточной в точке P в теории дизайна.
Конечная плоскость Мёбиуса порядка m представляет собой тактическую конфигурацию с k = m + 1 точками на цикл, которая является 3-схемой , а именно 3-( m 2 + 1, m + 1, 1) -блочной схемой.
Вопрос, поднятый Дж. Дж. Сильвестром в 1893 году и окончательно решенный Тибором Галлаи, касался инцидентности конечного множества точек на евклидовой плоскости.
Теорема (Сильвестра-Галлаи) : Конечное множество точек на евклидовой плоскости либо коллинеарно , либо существует прямая, инцидентная ровно двум из этих точек.
Прямая, содержащая ровно две точки, в этом контексте называется обычной прямой . Вероятно, Сильвестр пришел к этому вопросу, размышляя о вложимости конфигурации Гессе.
Связанный результат — теорема де Брейна–Эрдёша . Николас Говерт де Брейн и Пол Эрдёш доказали результат в более общей ситуации проективных плоскостей, но он по-прежнему справедлив в евклидовой плоскости. Теорема такова: [14]
Как отметили авторы, поскольку их доказательство было комбинаторным, результат справедлив в более широком контексте, фактически в любой геометрии инцидентности, в которой есть уникальная прямая через каждую пару различных точек. Они также упоминают, что версию евклидовой плоскости можно доказать из теоремы Сильвестра-Галлаи с помощью индукции .
Ограничение на количество флагов, определяемое конечным набором точек и определяемых ими линий, задается формулой:
Теорема (Семереди–Троттера) : если на плоскости заданы n точек и m прямых, то число флагов (пар инцидентная точка-прямая) равно:
и эта граница не может быть улучшена, кроме как с точки зрения неявных констант.
Этот результат можно использовать для доказательства теоремы Бека.
Аналогичная граница для числа инцидентностей предполагается для инцидентностей точка-окружность, но известны только более слабые верхние границы. [15]
Теорема Бека гласит, что конечные наборы точек на плоскости попадают в одну из двух крайностей: в одной большая часть точек лежит на одной прямой, а в другой требуется большое количество прямых, чтобы соединить все точки.
Теорема утверждает существование положительных констант C , K таких, что для любых n точек плоскости верно по крайней мере одно из следующих утверждений:
В исходном рассуждении Бека C равно 100, а K — неопределенная константа; оптимальные значения C и K неизвестны .
Медиа, связанные с геометрией инцидентности на Wikimedia Commons