Геометрия падения - Incidence geometry

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

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

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

Структуры заболеваемости

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

Расстояние в структуре падения

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

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

Когда расстояние рассматривается в структуре инцидентности, необходимо упомянуть, как оно определяется.

Частичные линейные пространства

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

Частичное линейное пространство является структура заболеваемости , для которых следующие аксиомы верны:

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

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

Дополнительные ограничения обеспечиваются условиями регулярности:

RLk : Каждая линия имеет одинаковое количество очков. Если конечно это число часто обозначается k .

RPr : Каждая точка имеет одинаковое количество линий. Если конечно это число часто обозначается r .

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

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

Простейшее нетривиальное линейное пространство

Линейное пространство представляет собой частичное линейное пространство таким образом, что:

  • Каждая пара различных точек определяет ровно одну линию.

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

  • Есть как минимум две различные линии.

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

Каждое нетривиальное линейное пространство содержит не менее трех точек и трех прямых, поэтому простейшее нетривиальное линейное пространство, которое может существовать, - это треугольник.

Линейное пространство, имеющее не менее трех точек на каждой линии, - это план Сильвестра – Галлая .

Основные геометрические примеры

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

Проективные плоскости

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

  • Каждая пара различных прямых пересекается ровно в одной точке,

и это удовлетворяет условию невырожденности:

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

Между P и L существует биекция на проективной плоскости. Если P - конечное множество, проективная плоскость называется конечной проективной плоскостью. Порядок конечной проективной плоскости п = к - 1 , то есть, на один меньше , чем количество точек на линии. Все известные проективные плоскости имеют порядки простых степеней . Проективная плоскость порядка n - это конфигурация (( n 2 + n + 1) n + 1 ) .

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

Проективная плоскость порядка 2
плоскость Фано

Самолет Фано

Эта знаменитая геометрия инцидентности была разработана итальянским математиком Джино Фано . В своей работе по доказательству независимости множества аксиом для проективного n -пространства, которое он разработал, он построил конечное трехмерное пространство с 15 точками, 35 линиями и 15 плоскостями, в которых каждая линия имела только три точки. Самолеты в этом пространстве состояли из семи точек и семи линий и теперь известны как плоскости Фано .

Плоскость Фано не может быть представлена ​​на евклидовой плоскости, используя только точки и отрезки прямых (т. Е. Она не реализуема). Это следствие теоремы Сильвестра – Галлаи , согласно которой каждая реализуемая геометрия инцидентности должна включать обычную линию , линию, содержащую только две точки. На плоскости Фано такой линии нет (то есть это конфигурация Сильвестра – Галлаи ), поэтому она не реализуема.

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

Аффинные плоскости

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

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

и удовлетворяющие условию невырожденности:

  • Существует треугольник, т.е. три неколлинеарные точки.

Прямые l и m в формулировке аксиомы Плейфэра называются параллельными . Каждую аффинную плоскость можно однозначно продолжить до проективной плоскости. Порядок конечной аффинной плоскости к , число точек на одной линии. Аффинная плоскость порядка n - это конфигурация (( n 2 ) n + 1 , ( n 2 + n ) n ) .

Аффинная плоскость порядка 3
(конфигурация Гессе)

Конфигурация Гессена

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

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

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

Частичная геометрия

Частичная геометрия pg (2,2,1)

Для целого числа α ≥ 1 тактическая конфигурация удовлетворяет:

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

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

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

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

Обобщенные многоугольники

Для п > 2 , А обобщенный п -угольник представляет собой частичное линейное пространство, частота графа Γ обладает свойством:

  • Распорка из Г (длина самого короткого цикла ) в два раза больше диаметра из Г (наибольшее расстояние между двумя вершинами, п в данном случае).

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

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

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

Рядом с полигонами

Для неотрицательного целого числа г а около 2 г -угольника является частота структура таким образом, что:

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

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

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

Самолеты Мебиуса

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

В частности, плоскость Мёбиуса представляет собой структуру инцидентности точек и циклов, такую ​​что:

  • Каждая тройка различных точек инцидентна ровно одному циклу.
  • Для любого флага ( P , z ) и любой точки Q, не инцидентной z, существует единственный цикл z с P I z , Q I z и zz = { P }. (Циклы называются прикоснуться в P .)
  • Каждый цикл имеет не менее трех точек и существует хотя бы один цикл.

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

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


Теоремы инцидентности на евклидовой плоскости

Теорема Сильвестра-Галлаи

Вопрос, поднятый Дж. Дж. Сильвестром в 1893 году и окончательно решенный Тибором Галлаи, касался падения конечного множества точек на евклидовой плоскости.

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

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

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

Связанный результат - теорема де Брейна – Эрдеша . Николаас Говерт де Брёйн и Поль Эрдеш доказали результат в более общих условиях проективных плоскостей, но он все еще верен в евклидовой плоскости. Теорема такова:

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

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

Теорема Семереди – Троттера.

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

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

и эту границу нельзя улучшить, кроме как с точки зрения неявных констант.

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

Аналогичная оценка числа инцидентов гипотетически построена для инцидентностей точка-окружность, но известны только более слабые оценки сверху.

Теорема Бека

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

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

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

В исходном аргументе Бека C равно 100, а K - неопределенная константа; не известно , что оптимальные значения C и K являются.

Еще примеры

Смотрите также

Примечания

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

внешние ссылки