Граф Шлефли

Граф Шлефли
Граф Шлефли
Вершин	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 принадлежит единственному подграфу, образованному прямым произведением полных графов K₆ $\text{[math]}$ $\text{[math]}$ $\square$ K₂, в котором вершины u и v принадлежат различным K₆ подграфам произведения. Граф Шлефли содержит 36 подграфов такого вида, один из которых состоит из векторов с координатами 0 и 1 в восьмимерном пространстве, как было описано выше^[2].

УльтраоднородностьПравить

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

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

ЗамечанияПравить

↑ ¹ ² D. A. Holton, J. Sheehan. The Petersen Graph. — Cambridge University Press, 1993. — С. 270–271.
↑ ¹ ² 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

[hs93-1] ¹ ² D. A. Holton, J. Sheehan. The Petersen Graph. — Cambridge University Press, 1993. — С. 270–271.

[bn92-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]