Граф Шлефли

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Шлефли
Изображение
Вершин

27

Рёбер

216

Хроматическое число

9

Свойства

Сильно регулярный
Без клешней

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

Конструкция[править | править вики-текст]

Граф пересечений 27 прямых на кубической поверхности[en] является дополнением графа Шлефли. Таким образом, две вершины смежны в графе Шлефли тогда и только тогда, когда соответствующие прямые являются скрещивающимися[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 прямых принадлежат единственной конфигурации[en] двойной шестёрки Шлефли — набору из 12 прямых, пересечение которых образует корону. Соответственно, в графе Шлефли каждое ребро uv принадлежит единственному подграфу, образованному прямым произведением полных графов K6 \square K2, в котором вершины u и v принадлежат различным K6 подграфам произведения. Граф Шлефли содержит 36 подграфов такого вида, один из которых состоит из векторов с координатами 0 и 1 в восьмимерном пространстве, как было описано выше[2].

Ультраоднородность[править | править вики-текст]

Граф называется k-ультраоднородным[en], если любой изоморфизм между двумя его порождёнными подграфами, содержащими не более 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.
  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.

Ссылки[править | править вики-текст]