Обобщенный многоугольник - Википедия - Generalized polygon

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

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

Определение

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

За ${ Displaystyle п geq 3}$ обобщенный п-gon - это структура заболеваемости ( ${ displaystyle P, L, I}$ ), куда ${ displaystyle P}$ это множество точек, ${ displaystyle L}$ это набор линий и ${ displaystyle I substeq P times L}$ это отношение инцидентности, такое, что:

Это частичное линейное пространство.
В нем нет обычного м-угольники как субгеометрия для ${ Displaystyle 2 Leq м <п}$ .
Имеет обыкновенный п-угольник как субгеометрия.
Для любого ${ Displaystyle {A_ {1}, A_ {2} } substeq P чашка L}$ существует подгеометрия ( ${ displaystyle P ', L', I '}$ ) изоморфна обычному п-гон такой, что ${ displaystyle {A_ {1}, A_ {2} } substeq P ' cup L'}$ .

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

В обхват графика заболеваемости в два раза больше диаметр п графика заболеваемости.

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

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

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

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

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

Примеры

Граф инцидентности обобщенного двуугольника - это полный двудольный граф K_s+1,т+1.
Для любых натуральных п ≥ 3, рассмотрим границу обычного многоугольник с п стороны. Объявите вершины многоугольника точками, а стороны линиями, с включением множества в качестве отношения инцидентности. Это приводит к обобщенному п-гон с s = т = 1.
Для каждого группа лиева типа грамм ранга 2 существует ассоциированный обобщенный п-угольник Икс с п равным 3, 4, 6 или 8 таким, что грамм действует транзитивно на множестве флагов Икс. В конечном случае при п = 6, получается разделенный шестиугольник Кэли порядка (q, q) за грамм₂(q) и закрученный шестиугольник тройственности порядка (q³, q) за ³D₄(q³), и для п = 8, получаем восьмиугольник Ри-Титса порядка (q, q²) за ²F₄(q) с q = 2^2п+1. С точностью до двойственности это единственные известные толстые конечные обобщенные шестиугольники или восьмиугольники.

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

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

2, 3, 4, 6 или 8.

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

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

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

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

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

куда q это основная сила.

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

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

куда q является нечетной степенью двойки.

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

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

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

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

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

Рекомендации

^ Черлин, Грегори (2005). «Локально конечные обобщенные четырехугольники с не более чем пятью точками на прямой». Дискретная математика. 291 (1–3): 73–79. Дои:10.1016 / j.disc.2004.04.021.
^ Таннер, Р. Майкл (1984). «Явные концентраторы из обобщенных N-угольников». Журнал SIAM по алгебраическим и дискретным методам. 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), «Отсутствие некоторых обобщенных многоугольников», Журнал алгебры, 1 (2): 114–131, Дои:10.1016/0021-8693(64)90028-6, МИСТЕР 0170955.

Haemers, W. H .; Роос, К. (1981), "Неравенство для обобщенных шестиугольников", Geometriae Dedicata, 10 (1–4): 219–222, Дои:10.1007 / BF01447425, МИСТЕР 0170955.

Кантор, В. М. (1986). «Обобщенные многоугольники, SCAB и GAB». Здания и геометрия диаграмм. Конспект лекций по математике. 1181. Шпрингер-Верлаг, Берлин. С. 79–158. CiteSeerX 10.1.1.74.3986. Дои:10.1007 / BFb0075513. ISBN 978-3-540-16466-1.

Ван Малдегем, Хендрик (1998), Обобщенные многоугольники, Монографии по математике, 93, Базель: Birkhäuser Verlag, Дои:10.1007/978-3-0348-0271-0, ISBN 978-3-7643-5864-8, МИСТЕР 1725957.
Стэнтон, Деннис (1983), "Обобщенный п-угольники и многочлены Чебычева », Журнал комбинаторной теории, Серия А, 34 (1): 15–27, Дои:10.1016/0097-3165(83)90036-5, МИСТЕР 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 по алгебраическим и дискретным методам. 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]