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

Обобщенное понятие структуры инцидентности полигонов

Разделенный шестиугольник Кэли 2-го порядка

В математике обобщенный многоугольник — это структура инцидентности, введенная Жаком Титсом в 1959 году. Обобщенные n -угольники охватывают в качестве частных случаев проективные плоскости (обобщенные треугольники, n = 3) и обобщенные четырехугольники ( n = 4). Многие обобщенные многоугольники возникают из групп типа Ли , но есть и экзотические, которые не могут быть получены таким образом. Обобщенные многоугольники, удовлетворяющие техническому условию, известному как свойство Муфанг , были полностью классифицированы Титсом и Вайсом. Каждый обобщенный n -угольник с четным n также является почти многоугольником .

Определение

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

Для обобщенного n -угольника есть структура инцидентности ( ), где — множество точек, — множество прямых, а — отношение инцидентности , такое, что: ${\displaystyle n\geq 3}$ ${\displaystyle P,L,I}$ ${\displaystyle P}$ ${\displaystyle L}$ ${\displaystyle I\subseteq P\times L}$

• Это частичное линейное пространство .
• Он не имеет обычных m -угольников в качестве подгеометрии для . ${\displaystyle 2\leq m<n}$
• В качестве подгеометрии он имеет обычный n -угольник.
• Для любого существует подгеометрия ( ), изоморфная обычному n -угольнику, такая, что . ${\displaystyle \{A_{1},A_{2}\}\subseteq P\cup L}$ ${\displaystyle P',L',I'}$ ${\displaystyle \{A_{1},A_{2}\}\subseteq P'\cup L'}$

Эквивалентный, но иногда более простой способ выразить эти условия: рассмотрим двудольный граф инцидентности с множеством вершин и ребрами, соединяющими инцидентные пары точек и линий. ${\displaystyle P\cup L}$

• Обхват графа инцидентности в два раза больше диаметра n графа инцидентности.

Из этого должно быть ясно, что графы инцидентности обобщенных многоугольников являются графами Мура .

Обобщенный многоугольник имеет порядок (s,t), если:

• все вершины графа инцидентности, соответствующие элементам, имеют одинаковую степень s + 1 для некоторого натурального числа s ; другими словами, каждая строка содержит ровно s + 1 точек, ${\displaystyle L}$
• все вершины графа инцидентности, соответствующие элементам, имеют одинаковую степень t + 1 для некоторого натурального числа t ; другими словами, каждая точка лежит ровно на t + 1 прямой. ${\displaystyle P}$

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

Двойственный обобщенному n -угольнику ( ), является структура инцидентности с обратным понятием точек и линий, а отношение инцидентности принимается как обратное отношение . Можно легко показать, что это снова обобщенный n -угольник. ${\displaystyle P,L,I}$ ${\displaystyle I}$

Примеры

• Граф инцидентности обобщенного двуугольника является полным двудольным графом K _{s +1, t +1} .
• Для любого натурального n ≥ 3 рассмотрим границу обычного многоугольника с n сторонами. Объявим вершины многоугольника точками, а стороны прямыми, с включением множеств в качестве отношения инцидентности. Это приведет к обобщенному n -угольнику с s = t = 1.
• Для каждой группы типа Ли G ранга 2 существует связанный обобщенный n -угольник X с n , равным 3, 4, 6 или 8, такой, что G действует транзитивно на множестве флагов X. В конечном случае для n=6 получается расщепляемый шестиугольник Кэли порядка ( q , q ) для G ₂ ( q ) и скрученный шестиугольник триальности порядка ( ^q3 , q ) для 3 D 4 ( q3 ) , а для ⁿ =8 получается восьмиугольник Ри-Титса порядка ( q , q2 ) для 2 F 4 ( q ) с q = 2 ^{2 n +1} . С точностью до двойственности это единственные известные толстые конечные обобщенные шестиугольники или восьмиугольники.

Ограничение по параметрам

Уолтер Фейт и Грэм Хигман доказали, что конечные обобщенные n -угольники порядка ( s , t ) с s  ≥ 2, t  ≥ 2 могут существовать только для следующих значений n :

2, 3, 4, 6 или 8. Другое доказательство результата Фейта-Хигмана было дано Килмойером и Соломоном.

Обобщенные «n»-угольники для этих значений называются обобщенными двуугольниками, треугольниками, четырехугольниками, шестиугольниками и восьмиугольниками.

Когда теорема Фейта-Хигмана объединяется с неравенствами Хемерса-Рооса, мы получаем следующие ограничения:

• Если n = 2, то граф инцидентности является полным двудольным графом и, таким образом, «s», «t» могут быть произвольными целыми числами.
• Если n = 3, структура представляет собой конечную проективную плоскость , а s = t .
• Если n = 4, то структура представляет собой конечный обобщенный четырехугольник , и t ^1/2 ≤ s ≤ t ² .
• Если n = 6, то st — квадрат , и t ^1/3 ≤ s ≤ t ³ .
• Если n = 8, то 2st — квадрат, и t ^1/2 ≤ s ≤ t ² .
• Если допускается, чтобы s или t были равны 1, а структура не является обычным n -угольником, то, помимо уже перечисленных значений n , возможно только n = 12.

Каждый известный конечный обобщенный шестиугольник порядка ( s , t ) для s , t > 1 имеет порядок

• ( q , q ): разделенные шестиугольники Кэли и их двойственные,
• ( q ³ , q ): скрученный триадный шестиугольник, или
• ( q , q ³ ): двойной скрученный триадный шестиугольник,

где q — степень простого числа.

Каждый известный конечный обобщенный восьмиугольник порядка ( s , t ) для s , t > 1 имеет порядок

• ( q , q ² ): восьмиугольник Ри-Титса или
• ( q ² , q ): двойной восьмиугольник Ри-Титса,

где q — нечетная степень числа 2.

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

Если s и t оба бесконечны, то обобщенные многоугольники существуют для каждого n, большего или равного 2. Неизвестно, существуют ли обобщенные многоугольники с одним из параметров конечным (и большим 1 ), а другим бесконечным (эти случаи называются полуконечными ). Питер Кэмерон доказал несуществование полуконечных обобщенных четырехугольников с тремя точками на каждой прямой, в то время как Андрис Брауэр и Билл Кантор независимо доказали случай четырех точек на каждой прямой. Результат о несуществовании для пяти точек на каждой прямой был доказан Г. Черлином с помощью теории моделей . ^[1] Такие результаты неизвестны без каких-либо дополнительных предположений для обобщенных шестиугольников или восьмиугольников, даже для наименьшего случая трех точек на каждой прямой.

Комбинаторные приложения

Как было отмечено ранее, графы инцидентности обобщенных многоугольников обладают важными свойствами. Например, каждый обобщенный n -угольник порядка (s,s) является клеткой (s+1,2n) . Они также связаны с графами-расширителями , поскольку обладают хорошими свойствами расширения. ^[2] Несколько классов экстремальных графов-расширителей получаются из обобщенных многоугольников. ^[3] В теории Рамсея графы, построенные с использованием обобщенных многоугольников, дают нам некоторые из наиболее известных конструктивных нижних границ для недиагональных чисел Рамсея. ^[4]

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

• Здание (математика)
• (Б, Н) пара
• Группа Ри
• Полигон Муфанг
• Рядом с полигоном

Ссылки

1. Черлин, Грегори (2005). «Локально конечные обобщенные четырехугольники с максимум пятью точками на линии». Дискретная математика . 291 (1–3): 73–79. doi : 10.1016/j.disc.2004.04.021 .
2. Таннер, Р. Майкл (1984). «Явные концентраторы из обобщенных N-угольников». Журнал SIAM по алгебраическим и дискретным методам . 5 (3): 287–293. doi :10.1137/0605030. hdl : 10338.dmlcz/102386 .
3. Нодзаки, Хироши (2014). «Границы линейного программирования для регулярных графов». arXiv : 1407.4562 [math.CO].
4. Косточка, Александр; Пудлак, Павел; Рёдль, Войтех (2010). «Некоторые конструктивные оценки чисел Рамсея». Журнал комбинаторной теории, серия B. 100 (5): 439–445. дои : 10.1016/j.jctb.2010.01.003 .

• Годсил, Крис ; Ройл, Гордон (2001), Алгебраическая теория графов , Graduate Texts in Mathematics, т. 207, Нью-Йорк: Springer-Verlag, doi :10.1007/978-1-4613-0163-9, ISBN 978-0-387-95220-8, г-н  1829620.
• Фейт, Уолтер ; Хигман, Грэм (1964), «Несуществование некоторых обобщенных многоугольников», Журнал алгебры , 1 (2): 114–131, doi : 10.1016/0021-8693(64)90028-6 , MR  0170955.

• Хемерс, WH; Роос, C. (1981), «Неравенство для обобщенных шестиугольников», Geometriae Dedicata , 10 (1–4): 219–222, doi :10.1007/BF01447425, MR  0608143.

• Kantor, WM (1986). "Обобщенные многоугольники, SCAB и GAB". Buildings and the Geometry of Diagrams . Lecture Notes in Mathematics. Vol. 1181. Springer-Verlag, Berlin. pp. 79–158. CiteSeerX  10.1.1.74.3986 . doi :10.1007/BFb0075513. ISBN 978-3-540-16466-1.
• Килмойер, Роберт; Соломон, Луис (1973), «О теореме Фейта-Хигмана», Журнал комбинаторной теории, Серия A , 15 (3): 310–322, doi : 10.1016/0097-3165(73)90076-9 , MR  0357157
• Ван Малдегем, Хендрик (1998), Обобщенные многоугольники , Монографии по математике, том. 93, Базель: Birkhäuser Verlag, номер документа : 10.1007/978-3-0348-0271-0, ISBN. 978-3-7643-5864-8, г-н  1725957.
• Стэнтон, Деннис (1983), «Обобщенные n -угольники и многочлены Чебышева», Журнал комбинаторной теории, Серия A , 34 (1): 15–27, doi : 10.1016/0097-3165(83)90036-5 , MR  0685208.
• Титс, Жак ; Вайс, Ричард М. (2002), Многоугольники Муфанга , Springer Monographs in Mathematics, Берлин: Springer-Verlag, ISBN 978-3-540-43714-7, г-н  1938841.