Граф Шлефли
| Граф Шлефли | |
|---|---|
 | |
| Вершин | 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.[источник не указан 534 дня] Единственными связными конечными графами этого типа являются полные графы, графы Турана, 3 × 3 ладейные графы и цикл с 5 вершинами. Бесконечный граф Радо счётно ультраоднороден.
Существует только два связных графа, которые 4-ультраоднородны, но не 5-ультраоднородны — это граф Шлефли и его дополнение. Доказательство основывается на классификации простых конечных групп[5][6][7].
Замечания[править | править код]
- ↑ 1 2 D. A. Holton, J. Sheehan. The Petersen Graph. — Cambridge University Press, 1993. — С. 270–271.
- ↑ 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.
- ↑ 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. Надо отметить, что Камерон и ван Линт использовали другие определения этих графов, по которому и граф Шлефли и граф Клебша являются дополнениями графам, определение которых дано здесь.
- ↑ Maria Chudnovsky, Paul Seymour. Surveys in combinatorics 2005. — Cambridge Univ. Press, 2005. — Т. 327. — С. 153–171. Архивировано 9 июня 2010 года.
- ↑ J. M. J. Buczak. Finite Group Theory. — Oxford University, 1980.
- ↑ Peter Jephson Cameron. 6-transitive graphs // Journal of Combinatorial Theory, Series B. — 1980. — Т. 28. — С. 168–179.
- ↑ Alice Devillers. Classification of some homogeneous and ultrahomogeneous structures. — Université Libre de Bruxelles, 2002.
Ссылки[править | править код]
- Weisstein, Eric W. Schläfli Graph (англ.) на сайте Wolfram MathWorld.
- Andries E. Brouwer page. Архивная копия от 1 июля 2014 на Wayback Machine