Почти многоугольник

Почти 2d-угольники — это структура инцидентности (${\displaystyle P,L,I}$), где ${\displaystyle P}$ — множество точек, ${\displaystyle L}$ — множество прямых, а ${\displaystyle I\subseteq P\times L}$ — отношение инцидентности, такое, что:

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

Заметим, что расстояние измеряется в терминах коллинеарного графа точек, т.е. графа, образованного из точек в качестве вершин, и пара вершин соединена ребром, если они инцидентны одной прямой. Мы можем также дать альтернативное определение в терминах теории графов. Почти 2d-угольник — это связный граф конечного диаметра d со свойством, что для любой вершины x и любой максимальной клики M существует единственная вершина x' в M, ближайшая к x. Максимальная клика такого графа соответствует прямым в определении структуры инцидентности. Почти 0-угольник (d = 0) — это единственная точка, в то время как почти 2-угольник (d = 1) — это просто одна прямая, т.е. полный граф. Почти квадрат (d = 2) — это то же самое, что и (возможно, вырожденный) обобщённый четырёхугольник. Можно показать, что любой обобщённый 2d-угольник является почти 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}$

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