Граф Шлефли

Граф Шлефли — 16-регулярный ненаправленный граф с 27 вершинами и 216 рёбрами. Граф назван в честь Людвига Шлефли. Это сильно регулярный граф с параметрами srg(27, 16, 10, 8).

Граф Шлефли
Вершин	27
Рёбер	216
Хроматическое число	9
Свойства	Сильно регулярный Без клешней
Медиафайлы на Викискладе

Конструкция

Граф пересечений 27 прямых на кубической поверхности является дополнением графа Шлефли. Таким образом, две вершины смежны в графе Шлефли тогда и только тогда, когда соответствующие прямые являются скрещивающимися^[1]

Граф Шлефли можно получить также из системы восьмимерных векторов

(1, 0, 0, 0, 0, 0, 1, 0),

(1, 0, 0, 0, 0, 0, 0, 1) и

(−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),

и 24 векторов, полученных перестановкой первых шести координат этих трёх векторов. Эти 27 векторов соответствуют вершинам графа Шлефли. Две вершины смежны тогда и только тогда, когда внутреннее произведение соответствующих двух векторов равно 1^[2].

Подграфы и окрестности

Окрестность любой вершины графа Шлефли есть подграф с 16 вершинами, в котором каждая вершина имеет 10 соседних вершин (числа 16 и 10 получаются как параметры графа Шлефли, когда он рассматривается как строго регулярный граф). Все эти подграфы изоморфны дополнению графа Клебша^[1][3]. Поскольку граф Клебша не содержит треугольников, граф Шлефли не содержит клешней. Этот факт играет важную роль в структурной теории графов без клешней, разработанной Марией Чудновской и Полом Сеймуром^[4].

Любые две скрещивающиеся прямые из этих 27 прямых принадлежат единственной конфигурации двойной шестёрки Шлефли — набору из 12 прямых, пересечение которых образует корону. Соответственно, в графе Шлефли каждое ребро uv принадлежит единственному подграфу, образованному прямым произведением полных графов K₆ ${\displaystyle \square }$ K₂, в котором вершины u и v принадлежат различным K₆ подграфам произведения. Граф Шлефли содержит 36 подграфов такого вида, один из которых состоит из векторов с координатами 0 и 1 в восьмимерном пространстве, как было описано выше^[2].

Ультраоднородность

Граф называется k-ультраоднородным^[англ.], если любой изоморфизм между двумя его порождёнными подграфами, содержащими не более k вершин, может быть продолжен до автоморфизма всего графа. Если граф 5-ультраоднороден, он ультраоднороден для любого k.^{[источник не указан 1063 дня]} Единственными связными конечными графами этого типа являются полные графы, графы Турана, 3 × 3 ладейные графы и цикл с 5 вершинами. Бесконечный граф Радо счётно ультраоднороден.

Существует только два связных графа, которые 4-ультраоднородны, но не 5-ультраоднородны — это граф Шлефли и его дополнение. Доказательство основывается на классификации простых конечных групп^[5][6][7].