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

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

Определение

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

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

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

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

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

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

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

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

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

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

Примеры

Граф инцидентности обобщенного двуугольника представляет собой полный двудольный граф 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 ) и скрученный шестиугольник тройственности порядка ( q ³, q ) для ³Д ₄ ( q ³) , а для n=8 получается восьмиугольник Ри-Титса порядка ( q , q ²) для ²F ₄ ( q ) с q = 2 ^{2н 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 ≤ с ≤ т ².
Если n = 6, то st — квадрат , а t ^1/3 ≤ с ≤ т ³.
Если n = 8, то 2-й квадрат, а t ^1/2 ≤ с ≤ т ².
Если s или t могут быть равны 1 и структура не является обычным n -угольником, тогда, помимо уже перечисленных значений n , только n = 12. возможно

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

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

Кантор, WM (1986). «Обобщенные полигоны, SCAB и GAB». Здания и геометрия диаграмм . Конспект лекций по математике. Том. 1181. Шпрингер-Верлаг, Берлин. стр. 79–158. CiteSeerX 10.1.1.74.3986 . дои : 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 по математике, Берлин: Springer-Verlag, ISBN 978-3-540-43714-7 , МР 1938841 .

[1] Черлин, Грегори (2005). «Локально конечные обобщенные четырехугольники с не более чем пятью точками на линии» . Дискретная математика . 291 (1–3): 73–79. дои : 10.1016/j.disc.2004.04.021 .

[2] Таннер, Р. Майкл (1984). «Явные концентраторы из обобщенных N-угольников». SIAM Journal по алгебраическим и дискретным методам . 5 (3): 287–293. дои : 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 .

[1]

[2]

[3]

[4]