В теорія графів графом Шлефлі — 16-регулярний ненаправлений граф із 27 вершинами і 216 ребрами. Граф названо на честь Людвіга Шлефлі. Це сильно регулярний граф із параметрами srg(27, 16, 10, 8).
Побудова Граф перетинів 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 виходять як параметри графа Шлефлі, коли його розглядаєти як строго регулярний граф). Всі ці підграфи ізоморфні доповненню графа Клебша Слід зауважити, що Камерон і ван Лінт використали інші визначення цих графів, за яким і граф Шлефлі і граф Клебша є доповненнями графів, визначення яких наведено тут.. Оскільки граф Клебша не містить трикутників, граф Шлефлі не містить клешень. Цей факт відіграє важливу роль у структурній теорії графів без клешень, яку розробили Марія Чудновська та .
Будь-які дві мимобіжні прямі з цих 27 прямих належать єдиній конфігурації подвійної шістки Шлефлі — набору з 12 прямих, перетин яких утворює корону. Відповідно, в графі Шлефлі кожне ребро uv належить єдиному підграфу, утвореному прямим добутком повного графа K6 K2, в якому вершини u і v належать різним K6 підграфам добутку. Граф Шлефлі містить 36 підграфів такого виду, один з яких складається з векторів з координатами 0 і 1 у восьмивимірному просторі, як описано вище.
Ультраоднорідність Граф називають , якщо будь-який ізоморфізм між двома його породженими підграфами, що містять не більше k вершин, можна продовжити до автоморфізму всього графа. Якщо граф 5-ультраоднорідний, він ультраоднорідний для будь-якого k. Єдині зв'язні скінченні графи цього типу — це повні графи, графи Турана, 3 × 3 турові графи і цикл із 5 вершинами. Нескінченний граф Радо зліченно ультраоднорідний. Існує тільки два зв'язних графи, які 4-ультраоднорідні, але не 5-ультраоднорідні — це граф Шлефлі і його доповнення. Доведення ґрунтується на класифікації простих скінченних груп.
Примітки
Посилання
Andries E. Brouwer page.