Граф Шлефлі

Граф Шлефлі
Граф Шлефлі
Вершин	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]. Оскільки граф Клебша не містить трикутників, граф Шлефлі не містить клешень. Цей факт відіграє важливу роль у структурній теорії графів без клешень, яку розробили Марія Чудновська та Пол Сеймур^[en][4].

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

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

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

Примітки

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. — 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.

Посилання

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