Русская Википедия:Обобщённый многоугольник
Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из Шаблон:Не переведено 5, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью классифицированы Титсом и Вайсом. Любой обобщённый n-угольник с чётным n является также почти многоугольником.
Определение
Обобщённый 2-угольник (дигон) — это структура инцидентности по меньшей мере с 2 точками и 2 прямыми, где каждая точка инцидентна каждой прямой.
Для <math>n \geq 3</math> обобщённый n-угольник — это структура инцидентности (<math>P,L,I</math>), где <math>P</math> — множество точек, <math>L</math> — множество прямых, а <math>I\subseteq P\times L</math> — отношение инцидентности, такое, что:
- Это частично линейное пространство.
- Оно не имеет обычных m-угольников в качестве подгеометрии для <math>2 \leq m < n</math>.
- Оно не имеет обычных n-угольников в качестве подгеометрии.
- Для любого <math> \{A_1, A_2\} \subseteq P \cup L </math> существует подгеометрия (<math> P', L', I' </math>), изоморфная n-угольнику, такому, что <math>\{A_1, A_2\} \subseteq P' \cup L' </math>.
Эквивалентный, но иногда более простой путь выразить эти условия следующий. Возьмём двудольный граф инцидентности с множеством вершин <math>P \cup L</math> и рёбра, соединяющие пары точек и прямых.
Отсюда должно быть ясно, что графы инцидентности обобщённых многоугольников являются графами Мура.
Обобщённый многоугольник имеет порядок (s,t), если
- все вершины графа инцидентности, соответствующие элементам <math>L</math>, имеют одну степень s + 1 для некоторого натурального числа s. Другими словами, любая прямая содержит в точности s + 1 точек,
- все вершины графа инцидентности, соответствующие элементам <math>P</math>, имеют одну степень t + 1 для некоторого натурального числа t. Другими словами, любая точка лежит в точности на t + 1 прямых.
Мы говорим, что обобщённый многоугольник является толстым, если любая точка (прямая) инцидентна по меньшей мере трём прямым (точкам). Все толстые обобщённые многоугольники имеют порядок.
Двойственной для обобщённого n-угольника (<math>P,L,I</math>) является структура инциденций, в которой точки и прямые меняются ролями, а отношением инцидентности, соответственно, становится обратное к <math>I</math> отношение. Можно легко показать, что двойственная структура также является обобщённым n-угольником.
Примеры
- Граф инцидентности обобщённого двуугольника — это полный двудольный граф Ks+1,t+1.
- Для любого натурального n ≥ 3 возьмём границу обычного многоугольника с n сторонами. Объявим вершины многоугольника точками, а стороны — прямыми. Отношение инцидентности — естественное. Получим обобщённый n-угольник с s = t = 1.
- Для любой Шаблон:Не переведено 5 ранга 2 существует ассоциированный обобщённый n-угольник X с n, равным 3, 4, 6 или 8, такой что G действует транзитивно на множестве флагов X. В конечном случае, для n=6, можно получить разбитый шестиугольник Кэли порядка (q, q) для Шаблон:Не переведено 5 и скрученный тройственный шестиугольник порядка (q3, q) для Шаблон:Не переведено 5, а для n=8 получаем восьмиугольник Ри — Титса порядка (q, q2) для Шаблон:Не переведено 5 с 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/2 ≤ s ≤ t2.
- Если n=6, то st — это квадрат и t1/3 ≤ s ≤ t3.
- Если n=8, то 2st — это квадрат и t1/2 ≤ s ≤ t2.
- Если 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].
См. также
Примечания
Литература
- ↑ Как немецкая, фамилия Feit читается Файт, но, поскольку Файт эмигрировал в США, чтение его фамилии там может быть другим.
- ↑ Шаблон:Cite web
- ↑ Explicit Concentrators from Generalized N-Gons | SIAM Journal on Algebraic Discrete Methods | Vol. 5, No. 3 | Society for Industrial and Applied Mathematics
- ↑ Шаблон:Cite web
- ↑ Те же самые границы чисел Рамсея Шаблон:Wayback, полученные Косточкой, Пудлаком и Рёдлем.
