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

В математике — обобщенный многоугольник это структура инцидентности, введенная Жаком Титсом в 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]