Граф Шлефлі

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

Граф Шлефлі
Граф Шлефлі
(Вершин)	27
(Ребер)	216
Хроматичне число	9
Властивості	сильно регулярний без клешень

Побудова

Граф перетинів 27 прямих на кубічній поверхні є доповненням графа Шлефлі. Таким чином, дві вершини суміжні в графі Шлефлі тоді й лише тоді, коли відповідні прямі мимобіжні

Граф Шлефлі можна отримати також із системи восьмивимірних векторів: (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.

Підграфи і сусідство

Окіл будь-якої вершини графа Шлефлі є підграфом з 16 вершинами, в якому кожна вершина має 10 сусідніх вершин (числа 16 і 10 виходять як параметри графа Шлефлі, коли його розглядаєти як строго регулярний граф). Всі ці підграфи ізоморфні доповненню графа Клебша. Оскільки граф Клебша не містить трикутників, граф Шлефлі не містить клешень. Цей факт відіграє важливу роль у структурній теорії графів без клешень, яку розробили Марія Чудновська та ^[en].

Будь-які дві мимобіжні прямі з цих 27 прямих належать єдиній конфігурації подвійної шістки Шлефлі — набору з 12 прямих, перетин яких утворює корону. Відповідно, в графі Шлефлі кожне ребро uv належить єдиному підграфу, утвореному прямим добутком повного графа K₆ ${\displaystyle \square }$ K₂, в якому вершини u і v належать різним K₆ підграфам добутку. Граф Шлефлі містить 36 підграфів такого виду, один з яких складається з векторів з координатами 0 і 1 у восьмивимірному просторі, як описано вище.

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

Граф називають ^[en], якщо будь-який ізоморфізм між двома його породженими підграфами, що містять не більше k вершин, можна продовжити до автоморфізму всього графа. Якщо граф 5-ультраоднорідний, він ультраоднорідний для будь-якого k. Єдині зв'язні скінченні графи цього типу — це повні графи, графи Турана, 3 × 3 турові графи і цикл із 5 вершинами. Нескінченний граф Радо зліченно ультраоднорідний. Існує тільки два зв'язних графи, які 4-ультраоднорідні, але не 5-ультраоднорідні — це граф Шлефлі і його доповнення. Доведення ґрунтується на класифікації простих скінченних груп.

Примітки

1. D. A. Holton, J. Sheehan. The Petersen Graph. — Cambridge University Press, 1993. — С. 270–271.
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. — . Слід зауважити, що Камерон і ван Лінт використали інші визначення цих графів, за яким і граф Шлефлі і граф Клебша є доповненнями графів, визначення яких наведено тут.
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.

Посилання

• Weisstein, Eric W. Граф Шлефлі(англ.) на сайті Wolfram MathWorld.
• Andries E. Brouwer page.[ 1 липня 2014 у Wayback Machine.]