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

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

Розбитий шестикутник Келі порядку 2

Визначення

Узагальнений 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) для ^[en] і скручений троїстий шестикутник порядку (q³, q) для ^[en], а для n=8 отримуємо восьмикутник Рі — Тітса порядку (q, q²) для ^[en] з q=2²ⁿ⁺¹. З точністю до двоїстості відомі тільки скінченні товсті узагальнені шестикутники і восьмикутники.

Обмеження на параметри

Вальтер Файт і Грем Хіґман довели, що скінченні узагальнені 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), а другий нескінченний (ці многокутники називають напівскінченними). ^[en] довів, що напівскінченних узагальнених чотирикутників з трьома точками на кожній прямій, не існує. ^[en] і Біл Кантор незалежно довели неіснування для чотирьох точок на прямій. Неіснування узагальнених чотирикутників для п'яти точок на кожній прямій довів Г. Черлін, використовуючи теорію моделей. Не відомо інших результатів без прийняття деяких додаткових припущень щодо узагальнених шестикутників або восьмикутників навіть для найменшого випадку трьох точок на кожній прямій.

Комбінаторні застосування

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

Див. також

• ^[en]
• (Пара (B, N))
• ^[ru]
• ^[en]
• (Майже многокутник)

Примітки

1. Як німецьке, прізвище Feit читається Файт, але, оскільки Файт емігрував до США, читання його прізвища там може відрізнятись.
2. Locally finite generalized quadrangles with at most five points per line
3. Explicit Concentrators from Generalized N-Gons | SIAM Journal on Algebraic Discrete Methods | Vol. 5, No. 3 | Society for Industrial and Applied Mathematics
4. http://arxiv.org/pdf/1407.4562.pdf
5. Ті самі межі чисел Рамсея, отримані Косточкою, Пудлаком і ^[en].

Література

• Godsil Chris, Royle Gordon. Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics) — . — DOI:10.1007/978-1-4613-0163-9.
• Feit Walter, Higman Graham. The nonexistence of certain generalized polygons // Journal of Algebra. — 1964. — Т. 1 (16 червня). — С. 114–131. — DOI:10.1016/0021-8693(64)90028-6.
• Haemers W. H., Roos C. An inequality for generalized hexagons // Geometriae Dedicata. — 1981. — Т. 10 (16 червня). — С. 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) — . — DOI:10.1007/978-3-0348-0271-0.
• Stanton Dennis. Generalized n-gons and Chebychev polynomials // . — 1983. — Т. 34, вип. 1 (16 червня). — С. 15–27. — (Series A). — DOI:10.1016/0097-3165(83)90036-5.
• Tits Jacques, Weiss Richard M. Moufang polygons. — Berlin : Springer-Verlag, 2002. — (Springer Monographs in Mathematics) — .