Граф Шлефли

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

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

Конструкция

Граф пересечений 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 принадлежит единственному подграфу, образованному прямым произведением полных графов K6 K2, в котором вершины u и v принадлежат различным K6 подграфам произведения. Граф Шлефли содержит 36 подграфов такого вида, один из которых состоит из векторов с координатами 0 и 1 в восьмимерном пространстве, как было описано выше[2].

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

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

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

Замечания

  1. ↑ 1 2 D. A. Holton, J. Sheehan. The Petersen Graph. — Cambridge University Press, 1993. — С. 270–271.
  2. ↑ 1 2 F. C. Bussemaker, A. Neumaier. Exceptional graphs with smallest eigenvalue-2 and related problems // Mathematics of Computation. — 1992. — Т. 59, вып. 200. — С. 583–608. — doi:10.1090/S0025-5718-1992-1134718-6.
  3. ↑ Peter Jephson Cameron, Jacobus Hendricus van Lint. Designs, graphs, codes and their links. — Cambridge University Press, 1991. — Т. 22. — С. 35. — ISBN 978-0-521-41325-1. Надо отметить, что Камерон и ван Линт использовали другие определения этих графов, по которому и граф Шлефли и граф Клебша являются дополнениями графам, определение которых дано здесь.
  4. ↑ Maria Chudnovsky, Paul Seymour. Surveys in combinatorics 2005. — Cambridge Univ. Press, 2005. — Т. 327. — С. 153–171. Архивировано 9 июня 2010 года.
  5. ↑ J. M. J. Buczak. Finite Group Theory. — Oxford University, 1980.
  6. ↑ Peter Jephson Cameron. 6-transitive graphs // Journal of Combinatorial Theory, Series B. — 1980. — Т. 28. — С. 168–179.
  7. ↑ Alice Devillers. Classification of some homogeneous and ultrahomogeneous structures. — Université Libre de Bruxelles, 2002.

Ссылки