Обобщённый многоугольник (KQkQp~uudw bukikrikl,unt)

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

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

Определение

[править | править код]

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

Для обобщённый n-угольник — это структура инцидентности (), где — множество точек, — множество прямых, а отношение инцидентности, такое, что:

  • Это частично линейное пространство.
  • Оно не имеет обычных m-угольников в качестве подгеометрии для .
  • Оно не имеет обычных n-угольников в качестве подгеометрии.
  • Для любого существует подгеометрия (), изоморфная n-угольнику, такому, что .

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

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

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

  • все вершины графа инцидентности, соответствующие элементам , имеют одну степень s + 1 для некоторого натурального числа s. Другими словами, любая прямая содержит в точности s + 1 точек,
  • все вершины графа инцидентности, соответствующие элементам , имеют одну степень t + 1 для некоторого натурального числа t. Другими словами, любая точка лежит в точности на t + 1 прямых.

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

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

  • Граф инцидентности обобщённого двуугольника — это полный двудольный граф Ks+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) для G2(q)[англ.] и скрученный тройственный шестиугольник порядка (q3, q) для 3D4(q3)[англ.], а для n=8 получаем восьмиугольник Ри — Титса порядка (q, q2) для 2F4(q)[англ.] с q=22n+1. С точностью до двойственности известны только конечные толстые обобщённые шестиугольники и восьмиугольники.

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

[править | править код]

Вальтер Файт[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, структура является конечным обобщённым четырёхугольником и t1/2st2.
  • Если n=6, то st — это квадрат и t1/3st3.
  • Если n=8, то 2st — это квадрат и t1/2st2.
  • Если s или t равно 1 и структура не является обычным n-угольником, то, кроме перечисленных выше значений n, возможно только значение n=12.

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

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

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

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

  • (q, q2) — восьмиугольник Ри — Титса, или
  • (q2, q) — двойственный восьмиугольнику Ри — Титса,

где q является нечётной степенью числа 2.

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

[править | править код]

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

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

[править | править код]

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

Примечания

[править | править код]
  1. Как немецкая, фамилия Feit читается Файт, но, поскольку Файт эмигрировал в США, чтение его фамилии там может быть другим.
  2. Locally finite generalized quadrangles with at most five points per line. Дата обращения: 20 августа 2017. Архивировано 29 июля 2021 года.
  3. Explicit Concentrators from Generalized N-Gons | SIAM Journal on Algebraic Discrete Methods | Vol. 5, No. 3 | Society for Industrial and Applied Mathematics
  4. Архивированная копия. Дата обращения: 20 августа 2017. Архивировано 22 августа 2017 года.
  5. Те же самые границы чисел Рамсея Архивная копия от 29 июля 2021 на Wayback Machine, полученные Косточкой, Пудлаком и Рёдлем.

Литература

[править | править код]
  • Godsil Chris, Royle Gordon. Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics). — ISBN 0-387-95220-9. — doi:10.1007/978-1-4613-0163-9.
  • Feit Walter, Higman Graham. The nonexistence of certain generalized polygons // Journal of Algebra. — 1964. — Т. 1. — С. 114–131. — doi:10.1016/0021-8693(64)90028-6.
  • Haemers W. H., Roos C. An inequality for generalized hexagons // Geometriae Dedicata. — 1981. — Т. 10. — С. 219-222. — doi:10.1007/BF01447425.
  • Kantor W. M. Generalized polygons, SCABs and GABs // Buildings and the Geometry of Diagrams. — Springer-Verlag, Berlin, 1986. — Т. 1181. — С. 79-158. — (Lecture Notes in Mathematics).
  • Van Maldeghem Hendrik. Generalized polygons. — Basel: Birkhäuser Verlag, 1998. — Т. 93. — (Monographs in Mathematics). — ISBN 3-7643-5864-5. — doi:10.1007/978-3-0348-0271-0.
  • Stanton Dennis. Generalized n-gons and Chebychev polynomials // Journal of Combinatorial Theory. — 1983. — Т. 34. — С. 15–27. — doi:10.1016/0097-3165(83)90036-5.
  • Tits Jacques, Weiss Richard M. Moufang polygons. — Berlin: Springer-Verlag, 2002. — (Springer Monographs in Mathematics). — ISBN 3-540-43714-2.