В математике , А обобщенный многоугольник является структура заболеваемости введено Жака Титса в 1959 году Обобщенных п -угольник охватывают , как частные случаи проективных плоскостей (обобщенные треугольники, п = 3) и обобщенные четырехугольники ( п = 4). Многие обобщенные многоугольники возникают из групп лиева типа , но есть и экзотические, которые нельзя получить таким способом. Обобщенные многоугольники, удовлетворяющие техническому условию, известному как свойство Муфанг , были полностью классифицированы Титсом и Вайссом. Каждый обобщенный n -угольник сn even также является близким многоугольником .
Определение
Обобщенный 2 -угольник (или двуугольник) - это структура инцидентности, состоящая как минимум из 2 точек и 2 линий, где каждая точка инцидентна каждой линии.
Для обобщенный n -угольник - это структура инцидентности (), где это множество точек, это набор линий и это отношение инцидентности , такое что:
- Это частичное линейное пространство .
- Он не имеет обычных m -угольников в качестве подгеометрии для.
- Он имеет обыкновенный n -угольник в качестве подгеометрии.
- Для любой существует подгеометрия (), изоморфный обычному n -угольнику такой, что.
Эквивалентный, но иногда более простой способ выразить эти условия: рассмотрим двудольный граф инцидентности с множеством вершин и ребра, соединяющие падающие пары точек и прямых.
Из этого должно быть ясно, что графы инцидентности обобщенных многоугольников являются графами Мура .
Обобщенный многоугольник имеет порядок (s, t), если:
- все вершины графа инцидентности, соответствующие элементам имеют одинаковую степень s + 1 для некоторого натурального числа s ; другими словами, каждая строка содержит ровно s + 1 точку,
- все вершины графа инцидентности, соответствующие элементам имеют одинаковую степень t + 1 для некоторого натурального числа t ; другими словами, каждая точка лежит ровно на t + 1 прямой.
Мы называем обобщенный многоугольник толстым, если каждая точка (прямая) инцидентна по крайней мере трем прямым (точкам). Все толстые обобщенные многоугольники имеют порядок.
Двойник обобщенного n -угольника (), Структура заболеваемости с понятием точек и линий отмененных и отношением инцидентности , принятым быть обратное соотношение из. Легко показать, что это снова обобщенный n -угольник.
Примеры
- Граф инцидентности обобщенного двуугольника - это полный двудольный граф K s +1, t +1 .
- Для любого натурального n ≥ 3 рассмотрим границу обычного многоугольника с n сторонами. Объявите вершины многоугольника точками, а стороны линиями, с включением множества в качестве отношения инцидентности. Это приводит к обобщенному n -угольнику с s = t = 1.
- Для каждой группы Ли типа G ранга 2 есть соответствующие обобщенные п -угольник Х с п равно 3, 4, 6 или 8 таким образом, что G действует транзитивно на множестве флагов X . В конечном случае, для n = 6 , получается расщепленный шестиугольник Кэли порядка ( q , q ) для G 2 ( q ) и скрученный тройственный шестиугольник порядка ( q 3 , q ) для 3 D 4 ( q 3 ) , а для n = 8 получается восьмиугольник Ри-Титса порядка ( q , q 2 ) для 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 2 .
- Если п = 6, то й является квадрат , и т 1/3 ≤ s ≤ т 3 .
- Если n = 8, то 2-й квадрат и t 1/2 ≤ s ≤ t 2 .
- Если s или t могут быть равны 1, а структура не является обычным n -угольником, тогда, помимо уже перечисленных значений n , возможно только n = 12.
Каждый известный конечный обобщенный шестиугольник порядка ( s , t ) для s , t > 1 имеет порядок
- ( q , q ): расщепленные шестиугольники Кэли и их двойники,
- ( q 3 , q ): закрученный шестиугольник тройственности, или
- ( q , q 3 ): двойной скрученный шестиугольник тройственности,
где q - степень простого числа.
Каждый известный конечный обобщенный восьмиугольник порядка ( s , t ) для s , t > 1 имеет порядок
- ( q , q 2 ): восьмиугольник Ри-Титса или
- ( q 2 , q ): двойной восьмиугольник Ри-Титса,
где q - нечетная степень двойки.
Полуконечные обобщенные многоугольники
Если s и t оба бесконечны, то обобщенные многоугольники существуют для каждого n, большего или равного 2. Неизвестно, существуют ли обобщенные многоугольники с одним из параметров конечным (и большим, чем 1 ), а другой - бесконечным (эти случаи называется полуконечным ). Питер Кэмерон доказал отсутствие полуконечных обобщенных четырехугольников с тремя точками на каждой прямой, в то время как Андрис Брауэр и Билл Кантор независимо друг от друга доказали случай четырех точек на каждой прямой. Результат о несуществовании пяти точек на каждой прямой был доказан Г. Черлином с использованием теории моделей . [1] Никакие такие результаты не известны без каких-либо дополнительных предположений для обобщенных шестиугольников или восьмиугольников, даже для самого маленького случая трех точек на каждой линии.
Комбинаторные приложения
Как отмечалось ранее, графики инцидентности обобщенных многоугольников обладают важными свойствами. Например, каждый обобщенный n -угольник порядка (s, s) является (s + 1,2n) клеткой . Они также связаны с графами-расширителями, поскольку обладают хорошими свойствами расширения. [2] Несколько классов экстремальных расширительных графов получаются из обобщенных многоугольников. [3] В теории Рамсея графы, построенные с использованием обобщенных многоугольников, дают нам одни из наиболее известных конструктивных нижних оценок недиагональных чисел Рамсея. [4]
Смотрите также
Рекомендации
- ^ Черлин, Грегори (2005). «Локально конечные обобщенные четырехугольники с максимум пятью точками на прямой» . Дискретная математика . 291 (1–3): 73–79. DOI : 10.1016 / j.disc.2004.04.021 .
- ^ Таннер, Р. Майкл (1984). «Явные концентраторы из обобщенных N-угольников». Журнал СИАМ по алгебраическим и дискретным методам . 5 (3): 287–293. DOI : 10.1137 / 0605030 . hdl : 10338.dmlcz / 102386 .
- ^ Нодзаки, Хироши (2014). «Границы линейного программирования для регулярных графов». arXiv : 1407.4562 [ math.CO ].
- ^ Косточка, Александр; Пудлак, Павел; Рёдль, Войтех (2010). «Некоторые конструктивные оценки чисел Рамсея». Журнал комбинаторной теории, серии B . 100 (5): 439–445. DOI : 10.1016 / j.jctb.2010.01.003 .
- Годсил, Крис ; Ройл, Гордон (2001), Алгебраическая теория графов , Тексты для выпускников по математике, 207 , Нью-Йорк: Springer-Verlag, DOI : 10.1007 / 978-1-4613-0163-9 , ISBN 978-0-387-95220-8, MR 1829620.
- Фейт, Вальтер ; Хигман, Грэхэм (1964), "Несуществование некоторых обобщенных многоугольников", журнал алгебры , 1 (2): 114-131, DOI : 10,1016 / 0021-8693 (64) 90028-6 , МР 0170955.
- Хемерс, WH; Roos, С. (1981), "Неравенство для обобщенных шестиугольников", Geometriae Dedicata , 10 (1-4): 219-222, DOI : 10.1007 / BF01447425 , МР 0608143.
- Кантор, WM (1986). «Обобщенные многоугольники, SCAB и GAB». Здания и геометрия диаграмм . Конспект лекций по математике. 1181 . Springer-Verlag, Берлин. С. 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, DOI : 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, MR 1938841.