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

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

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

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

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

An структура заболеваемости $(п, L, Я)$ состоит из набора $п$ чьи элементы называются точки, непересекающееся множество $L$ чьи элементы называются линии и отношение инцидентности $я$ между ними, то есть подмножество $п \times L$ чьи элементы называются флаги.^[2] Если $(А, л)$ это флаг, мы говорим, что $А$ является инцидент с $л$ или это $л$ инцидент с $А$ (отношение симметрично) и напишем $А я л$ . Интуитивно понятно, что точка и линия находятся в этом отношении тогда и только тогда, когда точка на линия. Учитывая точку $B$ и линия $м$ которые не образуют флаг, то есть точка не на линии, пара $(B, м)$ называется анти-флаг.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А линейное пространство частичное линейное пространство такое, что:^[7]

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

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

Есть как минимум две различные линии.^[8]

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

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

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

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

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

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

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

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

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

Всего существует четыре точки, ни одна из трех коллинеарен.

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

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

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

Самолет Фано

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

Самолет Фано не может быть представлен в Евклидова плоскость используя только точки и отрезки прямых (т.е. нереализуемо). Это следствие Теорема Сильвестра – Галлаи, согласно которому каждая реализуемая геометрия падения должна включать обычная линия, строка, содержащая всего две точки. У плоскости Фано такой линии нет (т. Е. Это Конфигурация Сильвестра-Галлая ), поэтому это неосуществимо.^[12]

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

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

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

Для любой точки $А$ и линия $л$ не инцидент с этим ( анти-флаг) есть ровно одна строка $м$ инцидент с $А$ (это, $А я м$ ), что не соответствует $л$ (известный как Аксиома Playfair ),

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

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

Линии $л$ и $м$ в формулировке аксиомы Playfair называются параллельно. Каждую аффинную плоскость можно однозначно продолжить до проективной плоскости. В порядок конечной аффинной плоскости есть $k$ , количество точек на линии. Аффинная плоскость порядка $п$ является $((п 2) п + 1, (п 2 + п) п)$ конфигурация.

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

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

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

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

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

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

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

Учитывая целое число $α \geq 1$ , тактическая конфигурация, удовлетворяющая:

Для каждого антифлага $(B, м)$ есть $α$ флаги $(А, л)$ такой, что $B я л$ и $А я м$ ,

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

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

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

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

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

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

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

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

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

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

Для неотрицательного целого числа $d$ а около $2 d$ -угольник представляет собой такую структуру инцидентов, что:

Максимальное расстояние (измеренное на графике коллинеарности) между двумя точками составляет $d$ , и
За каждую точку $Икс$ и линия $л$ есть уникальная точка на $л$ что ближе всего к $Икс$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В проективная плоскость, каждый неколлинеарный набор

п

очков определяет как минимум

п

четкие линии.

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

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

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

Теорема (Семереди – Троттер).: данный $п$ очки и $м$ линий на плоскости, количество флажков (падающих пар точек-линий) составляет:

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

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

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

Теорема Бека

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

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

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

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

Еще примеры

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

Заметки

^ Как, например, это делает Л. Шторм в своей главе о конечной геометрии в Колборн и Диниц (2007), стр. 702)
^ Технически это структура инцидентности второго ранга, где ранг относится к количеству типов рассматриваемых объектов (здесь точек и линий). Также изучаются структуры более высокого ранга, но некоторые авторы ограничиваются случаем ранга два, и мы сделаем это здесь.
^ Мурхаус, стр.5
^ Дембовский 1968, п. 5
^ Кокстер, Х. С. М. (1969), Введение в геометрию, Нью-Йорк: John Wiley & Sons, стр. 233, г. ISBN 978-0-471-50458-0
^ Гильберт, Дэвид; Кон-Фоссен, Стефан (1952), Геометрия и воображение (2-е изд.), Челси, стр. 94–170, ISBN 978-0-8284-1087-8
^ Мурхаус, стр. 5
^ Есть несколько альтернатив этой аксиоме "нетривиальности". Это можно было бы заменить словами «существуют три точки не на одной линии», как это сделано в Баттен и Бойтельспахер (1993, стр. 1). Есть и другие варианты, но они всегда должны быть существование утверждения, исключающие очень простые случаи, которые нужно исключить.
^ Фано, Г. (1892), "Sui postulati fondamentali della geometria proiettiva", Giornale di Matematiche, 30: 106–132
^ Коллино, Конте и Верра, 2013 г., п. 6
^ Малькевич Конечная геометрия? Рекомендуемая колонка AMS
^ Айгнер и Зиглер (2010).
^ Использование $п$ в названии является стандартным, и его не следует путать с количеством точек в конфигурации.
^ Вайсштейн, Эрик В., "Теорема де Брейна – Эрдеша" от MathWorld

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

Айгнер, Мартин; Циглер, Гюнтер М. (2010), «Прямые на плоскости и разложения графов», Доказательства из книги, Берлин и Гейдельберг: Springer, стр. 63–67, Дои:10.1007/978-3-642-00856-6_10, ISBN 978-3-642-00855-9
Баттен, Линн Маргарет (1986), Комбинаторика конечных геометрий, Нью-Йорк: Издательство Кембриджского университета, ISBN 978-0-521-31857-0
Баттен, Линн Маргарет; Бойтельшпахер, Альбрехт (1993), Теория конечных линейных пространств, Нью-Йорк: Издательство Кембриджского университета, ISBN 978-0-521-33317-7
Бюкенхаут, Фрэнсис (1995), Справочник по геометрии падения: здания и фундаменты, Elsevier B.V.
Колборн, Чарльз Дж .; Диниц, Джеффри Х. (2007), Справочник комбинаторных схем (2-е изд.), Бока-Ратон: Chapman & Hall / CRC, ISBN 978-1-58488-506-1
Коллино, Альберто; Конте, Альберто; Верра, Алессандро (2013). «О жизни и научной деятельности Джино Фано». arXiv:1311.7177 [math.HO ].
Де Брюн, Барт (2016), Введение в геометрию падения, «Границы математики», издательство Springer International Publishing, Дои:10.1007/978-3-319-43811-5, ISBN 978-3-319-43810-8
Дембовский, Питер (1968), Конечная геометрия, Ergebnisse der Mathematik и ихрер Гренцгебиете, Band 44, Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-61786-0, Г-Н 0233275
Малькевич, Джо. "Конечная геометрия?". Получено 2 декабря, 2013.
Мурхаус, Дж. Эрик. «Геометрия падения» (PDF). Архивировано из оригинал (PDF) 29 октября 2013 г.. Получено 20 октября, 2012.
Юберберг, Йоханнес (2011), Основы геометрии падения, Монографии Springer по математике, Springer, Дои:10.1007/978-3-642-20972-7, ISBN 978-3-642-26960-8.
Шульт, Эрнест Э. (2011), Точки и линии, Universitext, Springer, Дои:10.1007/978-3-642-15627-4, ISBN 978-3-642-15626-7.
Бал, Симеон (2015), Конечная геометрия и комбинаторные приложения, Тексты студентов Лондонского математического общества, Издательство Кембриджского университета, ISBN 978-1107518438.

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

СМИ, связанные с Геометрия падения в Wikimedia Commons
система заболеваемости на Энциклопедия математики

[1] Как, например, это делает Л. Шторм в своей главе о конечной геометрии в Колборн и Диниц (2007), стр. 702)

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

[3] Мурхаус, стр.5

[4] Дембовский 1968, п. 5

[5] Кокстер, Х. С. М. (1969), Введение в геометрию, Нью-Йорк: John Wiley & Sons, стр. 233, г. ISBN 978-0-471-50458-0

[6] Гильберт, Дэвид; Кон-Фоссен, Стефан (1952), Геометрия и воображение (2-е изд.), Челси, стр. 94–170, ISBN 978-0-8284-1087-8

[7] Мурхаус, стр. 5

[8] Есть несколько альтернатив этой аксиоме "нетривиальности". Это можно было бы заменить словами «существуют три точки не на одной линии», как это сделано в Баттен и Бойтельспахер (1993, стр. 1). Есть и другие варианты, но они всегда должны быть существование утверждения, исключающие очень простые случаи, которые нужно исключить.

[9] Фано, Г. (1892), "Sui postulati fondamentali della geometria proiettiva", Giornale di Matematiche, 30: 106–132

[10] Коллино, Конте и Верра, 2013 г., п. 6

[11] Малькевич Конечная геометрия? Рекомендуемая колонка AMS

[FOOTNOTEAignerZiegler2010-12] Айгнер и Зиглер (2010).

[13] Использование $п$ в названии является стандартным, и его не следует путать с количеством точек в конфигурации.

[14] Вайсштейн, Эрик В., "Теорема де Брейна – Эрдеша" от MathWorld

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Структуры заболеваемости
Представление	Матрица заболеваемости График заболеваемости
Поля	Комбинаторика Блочный дизайн Система Штейнера Геометрия Заболеваемость Проективная плоскость Теория графов Гиперграф Статистика Блокировка
Конфигурации	Полный четырехугольник Самолет Фано Конфигурация Мебиуса – Кантора Конфигурация Pappus Конфигурация Гессен Конфигурация дезарга Конфигурация Рейя Шлефли двойная шестерка Конфигурация Кремона – Ричмонд Конфигурация Куммера Конфигурация Грюнбаума – Ригби Конфигурация Кляйна Двойной
Теоремы	Теорема Сильвестра-Галлаи Теорема Де Брейна – Эрдеша Теорема Семереди – Троттера. Теорема Бека Теорема Брука – Райзера – Чоула.
Приложения	Дизайн экспериментов Проблема школьницы Киркмана