Узагальнений многокутник
Узагальнений многокутник — це структура інцидентності, яку 1959 року запропонував Жак Тітс[en]. Узагальнені 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)[en] і скручений троїстий шестикутник порядку (q3, q) для 3D4(q3)[en], а для n=8 отримуємо восьмикутник Рі — Тітса порядку (q, q2) для 2F4(q)[en] з 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), а другий нескінченний (ці многокутники називають напівскінченними). Пітер Кемерон[en] довів, що напівскінченних узагальнених чотирикутників з трьома точками на кожній прямій, не існує. Ендрес Брюер[en] і Біл Кантор незалежно довели неіснування для чотирьох точок на прямій. Неіснування узагальнених чотирикутників для п'яти точок на кожній прямій довів Г. Черлін, використовуючи теорію моделей[2]. Не відомо інших результатів без прийняття деяких додаткових припущень щодо узагальнених шестикутників або восьмикутників навіть для найменшого випадку трьох точок на кожній прямій.
Комбінаторні застосування[ред. | ред. код]
Як зазначено вище, графи інцидентності узагальнених многокутників мають важливі властивості. Наприклад, будь-який узагальнений n-кутник порядку (s, s) є (s+1,2n) кліткою. Вони також пов'язані з експандерами, оскільки вони мають хороші властивості розширення[3]. Деякі класи екстремальних експандерів виходять з узагальнених многокутників[4]. У теорії Рамсея графи, побудовані за допомогою узагальнених многокутників, дають деякі кращі нижні межі недіагональних чисел Рамсея[5].
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ Як німецьке, прізвище Feit читається Файт, але, оскільки Файт емігрував до США, читання його прізвища там може відрізнятись.
- ↑ Locally finite generalized quadrangles with at most five points per line
- ↑ Explicit Concentrators from Generalized N-Gons | SIAM Journal on Algebraic Discrete Methods | Vol. 5, No. 3 | Society for Industrial and Applied Mathematics
- ↑ http://arxiv.org/pdf/1407.4562.pdf
- ↑ Ті самі межі чисел Рамсея, отримані Косточкою, Пудлаком і Редлем[en].
Література[ред. | ред. код]
- Godsil Chris, Royle Gordon. Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics) — ISBN 0-387-95220-9. — DOI:
- Feit Walter, Higman Graham. The nonexistence of certain generalized polygons // Journal of Algebra. — 1964. — Т. 1 (21 квітня). — С. 114–131. — DOI: .
- Haemers W. H., Roos C. An inequality for generalized hexagons // Geometriae Dedicata. — 1981. — Т. 10 (21 квітня). — С. 219-222. — DOI: .
- 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:
- Stanton Dennis. Generalized n-gons and Chebychev polynomials // Journal of Combinatorial Theory. — 1983. — Т. 34, вип. 1 (21 квітня). — С. 15–27. — (Series A). — DOI: .
- Tits Jacques, Weiss Richard M. Moufang polygons. — Berlin : Springer-Verlag, 2002. — (Springer Monographs in Mathematics) — ISBN 3-540-43714-2.