Граф Шлефлі
Шаблон:Граф В теорія графів графом Шлефлі — 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 вершин, можна продовжити до автоморфізму всього графа. Якщо граф 5-ультраоднорідний, він ультраоднорідний для будь-якого k. Єдині зв'язні скінченні графи цього типу — це повні графи, графи Турана, 3 × 3 турові графи і цикл із 5 вершинами. Нескінченний граф Радо зліченно ультраоднорідний. Існує тільки два зв'язних графи, які 4-ультраоднорідні, але не 5-ультраоднорідні — це граф Шлефлі і його доповнення. Доведення ґрунтується на класифікації простих скінченних груп[5][6][7].
Примітки
Посилання
- ↑ 1,0 1,1 Шаблон:Стаття
- ↑ 2,0 2,1 Шаблон:Стаття
- ↑ Шаблон:Стаття Слід зауважити, що Камерон і ван Лінт використали інші визначення цих графів, за яким і граф Шлефлі і граф Клебша є доповненнями графів, визначення яких наведено тут.
- ↑ Шаблон:Стаття
- ↑ Шаблон:Стаття
- ↑ Шаблон:Стаття
- ↑ Шаблон:Стаття