Узагальнений многокутник

Узагальнений 2-кутник (дигон) — це структура інцидентності щонайменше з 2 точками і 2 прямими, де кожна точка інцидентна кожній прямій.

Для ${\displaystyle n\geq 3}$ узагальнений n-кутник — це структура інцидентності (${\displaystyle P,L,I}$), де ${\displaystyle P}$ — множина точок, ${\displaystyle L}$ — множина прямих, а ${\displaystyle I\subseteq P\times L}$ — відношення інцидентності, таке, що:

• Це частково лінійний простір.
• Воно не має звичайних m-кутників як підгеометрій для ${\displaystyle 2\leq m<n}$.
• Воно не має звичайних n-кутників як підгеометрій.
• Для будь-якого ${\displaystyle \{A_{1},A_{2}\}\subseteq P\cup L}$ існує підгеометрія (${\displaystyle P',L',I'}$), ізоморфна n-кутнику, такому, що ${\displaystyle \{A_{1},A_{2}\}\subseteq P'\cup L'}$.

Еквівалентний, але іноді простіший спосіб виразити ці умови такий. Взявши двочастковий граф інцидентності зі множиною вершин ${\displaystyle P\cup L}$ і ребра, що з'єднують пари точок і прямих.

• Обхват графа інцидентності вдвічі більший від діаметра n графа інцидентності.

Звідси має бути ясно, що графи інцидентності узагальнених многокутників є графами Мура.

Узагальнений многокутник має порядок (s, t), якщо

• всі вершини графа інцидентності, відповідні елементам ${\displaystyle L}$, мають один степінь s+1 для деякого натурального числа s. Іншими словами, будь-яка пряма містить рівно s+1 точку,
• всі вершини графа інцидентності, відповідні елементам ${\displaystyle P}$, мають один степінь t+1 для деякого натурального числа t. Іншими словами, будь-яка точка лежить рівно на t+1 прямій.

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

Двоїстою для узагальненого n-кутника (${\displaystyle P,L,I}$) є структура інциденцій, у якій точки і прямі міняються ролями, а відношенням інцидентності, відповідно, стає обернене до ${\displaystyle 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) для ³D₄(q³), а для n=8 отримуємо восьмикутник Рі — Тітса порядку (q, q²) для ²F₄(q) з q=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 ≤ s ≤ t².
• Якщо n=6, то st — це квадрат і t^1/3 ≤ s ≤ t³.
• Якщо n=8, то 2st — це квадрат і t^1/2 ≤ s ≤ t².
• Якщо s або t дорівнює 1 і структура не є звичайним n-кутником, то, крім перерахованих вище значень n, можливе тільки значення n=12.

Будь-який відомий скінченний узагальнений шестикутник порядку (s, t) для s, t > 1 має порядок

• (q, q) — розділені шестикутники Келі і їх двоїстий,
• (q³, q) — скручений троїстий шестикутник, або
• (q, q³) — двоїстий скручений троїстий шестикутник, де q — степінь простого числа.

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

• (q, q²) — восьмикутник Рі — Тітса, або
• (q², q) — двоїстий восьмикутнику Рі — Тітса, де q є непарним степенем числа 2.

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

Як зазначено вище, графи інцидентності узагальнених многокутників мають важливі властивості. Наприклад, будь-який узагальнений n-кутник порядку (s, s) є (s+1,2n) кліткою. Вони також пов'язані з експандерами, оскільки вони мають хороші властивості розширення[3]. Деякі класи екстремальних експандерів виходять з узагальнених многокутників[4]. У теорії Рамсея графи, побудовані за допомогою узагальнених многокутників, дають деякі кращі нижні межі недіагональних чисел Рамсея[5].

• Будівля (математика)
• Пара (B, N)
• Група Рі
• Площина Муфанга
• Майже многокутник