Майже многокутник

Майже ${\displaystyle 2d}$-кутники — це структура інцидентності (${\displaystyle P,L,I}$), де ${\displaystyle P}$ — множина точок, ${\displaystyle L}$ — множина прямих, а ${\displaystyle I\subseteq P\times L}$ — відношення інцидентності, таке, що:

• Найбільша відстань між двома точками (так званий діаметр) дорівнює d.
• Для будь-якої точки ${\displaystyle x}$ і будь-якої прямої ${\displaystyle L}$ існує єдина точка на ${\displaystyle L}$, найближча до ${\displaystyle x}$.

Зауважимо, що відстань вимірюється в термінах колінеарного графу точок, тобто графу, утвореного з точок як вершин, і пара вершин з'єднана ребром, якщо вони інцидентні одній прямій. Ми можемо також дати альтернативне визначення в термінах теорії графів. Майже ${\displaystyle 2d}$-кутник — це зв'язний граф скінченного діаметра d з властивістю, що для будь-якої вершини x і будь-якої максимальної кліки M існує єдина вершина x у M, найближча до x. Максимальна кліка такого графу відповідає прямим у визначенні структури інцидентності. Майже 0-кутник (d = 0) — це єдина точка, тоді як майже 2-кутник (d = 1) — це просто одна пряма, тобто повний граф. Майже квадрат (d = 2) — це те саме, що й (можливо, вироджений) узагальнений чотирикутник. Можна показати, що будь-який узагальнений 2d-кутник є майже ${\displaystyle 2d}$-кутником, що задовольняє двом додатковим умовам:

• Будь-яка точка інцидентна щонайменше двом прямим.
• Для будь-яких двох точок x, y на відстані i < d існує єдина сусідня точка для y на відстані i − 1 від x.

Майже многокутник називають щільним, якщо будь-яка пряма інцидентна щонайменше трьом точкам і якщо дві точки на відстані два мають щонайменше дві спільні сусідні точки. Кажуть, що многокутник має порядок (s, t), якщо будь-яка пряма інцидентна рівно s + 1 точці і будь-яка точка інцидентна рівно t + 1 прямій. Щільні майже многокутники мають багату теорію і деякі їх класи (такі як тонкі щільні майже многокутники) повністю класифіковано[3].

Підпростір X простору P називають опуклим, якщо будь-яка точка на найкоротшому шляху між двома точками з X також міститься в X[4].

• Всі зв'язні двочасткові графи є майже многокутниками. Фактично, будь-який майже многокутник, що має рівно дві точки на пряму, повинен бути зв'язним двочастковим графом.
• Всі скінченні узагальнені многокутники, за винятком проективних площин.
• Всі двоїсті полярні простори.
• Майже восьмикутник Холла — Янко, відомий також як майже восьмикутник Коена — Тітса[5], пов'язаний з групою Холла — Янко. Його можна побудувати, вибравши клас спряженості 315 центральних інволюцій групи Холла — Янко як точки і триелементні підмножини {x, y, xy} як прямі, якщо x і y комутують.
• Майже многокутник M₂₄, пов'язаний з групою Матьє M₂₄ і розширеним двійковим кодом Голея. Восьмикутник будується з 759 октад (блоків) схеми Вітта S(5, 8, 24), що відповідають кодам Голея, як точок і трійок трьох попарно не перетинних вісімок як прямих.[6]
• Візьмемо розбиття множини {1, 2,…, 2n+2} на n+1 підмножину з 2 елементів як точки, і розбиття на n—1[7] підмножину з двох елементів і одну підмножину з 4 елементів як прямі. Точка інцидентна прямій тоді й лише тоді, коли вона (як розбиття) є уточненням прямої. Це дає нам 2n-кутник з трьома точками на кожній прямій, який зазвичай позначаються як H_n. Повна група автоморфізмів цього майже многокутника — S_2n+2[8].

Скінченний майже ${\displaystyle 2d}$-кутник S називають правильним, якщо він має порядок ${\displaystyle (s,t)}$ і якщо існують константи ${\displaystyle t_{i},i\in \{1,\ldots ,d\}}$, такі, що для будь-яких двох точок ${\displaystyle x}$ і ${\displaystyle y}$ на відстані ${\displaystyle i}$ існує рівно ${\displaystyle t_{i}+1}$ прямих, що проходять через ${\displaystyle y}$ і містять (обов'язково єдину) точку на відстані ${\displaystyle i-1}$ від ${\displaystyle x}$. Виявляється, що правильні майже ${\displaystyle 2d}$- кутники — це точно ті майже ${\displaystyle 2d}$-кутники, точкові графи яких є дистанційно-регулярними графами. Узагальнений ${\displaystyle 2d}$-кутник порядку ${\displaystyle (s,t)}$ — це правильний майже ${\displaystyle 2d}$-кутник з параметрами ${\displaystyle t_{1}=0,t_{2}=0,\ldots ,t_{d}=t}$.

• Скінченна геометрія
• Полярний простір
• Частково лінійний простір
• Схема відношення
• Граф Голла — Янко