Граф Гофмана — Синглтона

Граф Гофмана — Синглтона
Названо на честь	Алан Гофман[en] Роберт Синглтон
Вершин	50
Ребер	175
Радіус	2
Діаметр	2[1]
Обхват	5[1]
Автоморфізм	252 000 (PSU(3,52):2)[2]
Хроматичне число	4
Хроматичний індекс	7[3]
Властивості	Сильно регулярний Симетричний Гамільтонів Цілий Клітка Граф Мура

У математичній теорії графів, граф Гофмана — Синглтона це 7-регулярний неорієнтований граф зі 50 вершинами і 175 ребрами. Це єдиний сильно регулярний граф із параметрами (50,7,0,1)^[4]. Його побудували Алан Гофман^[en] і Роберт Синглтон, коли намагалися класифікувати всі графи Мура, він є графом Мура з найвищим порядком, для якого відомо, що граф існує^[5]. Оскільки це граф Мура, в якому кожна вершина має степінь 7, а обхват 5, тоді він є (7,5)-кліткою.

Тут наведено дві побудови графа Гофмана — Синглтона.^[6]

Візьміть п'ять п'ятикутників P_h і п'ять пентаграми Q_i, так щоб вершина j з P_h була суміжною з вершинами j−1 та j+1 з P_h і вершина j з Q_i  була суміжною з вершинами j−2 та j+2 з Q_i. Тепер приєднайте вершину j з P_h до вершини h·i+j з Q_i. (Всі індекси за модулем 5.)^[6]

Будь-яку множину зі семи точок (як абстрактних математичних об'єктів) можна перетворити на площину Фано, додавши сім ліній на них. Кількість різних способів зробити це — 30 = 7!/168. Тут 7! — це число перестановок із семи точок. 168 — число симетрій площини Фано, і, як наслідок, кількість перестановок, які зберігають будь-який заданий набір ліній, які утворюють площину Фано. Серед цих 30 різних площин Фано, кожна підмножина трьох точок використовується як лінія в 6 з 30 площин. Для будь-якої з цих 30 площин Фано, є 14 інших, які розділяють принаймні один рядок з ними.

Також сама множина з семи точок теж має 35 різних підмножин, які складаються з трьох елементів («тріад»), підрахованих за допомогою біноміального коефіцієнта ${\displaystyle {\tbinom {7}{3}}=35}$.

Граф Гофмана — Синглтона в такому разі можна побудувати з двох множин вершин:

• по одній для кожної площини Фано в наборі з 15 площин, які формуються вибором однієї довільної і 14 інших, які розділяють лінію з ним, та
• по одній для кожної тріади.

Ці вершини з'єднані ребрами двох типів:

• між кожною вибраною площиною Фано і 7 тріад, які відповідають її лінії, та
• між тріадами зі спільних точок.^[6]

Група автоморфізмів графа Гофмана — Синглтона є групою порядку 252 000 ізоморфною PΣU(3,5²) напівпрямому добутку проєктивної спеціальної унітарної групи^[en] PSU(3,5²) з циклічною групою порядку 2, породженої автоморфізму Фробеніуса. Він діє транзитивно на вершини, ребра і дуги графа. Тому граф Гофмана — Синглтона симетричний граф. Стабілізатор вершини графа є ізоморфом симетричної групи S₇ по 7 букв. Стабілізатор множини ребер ізоморфний Aut(A₆)=A₆.2², де A₆ є знакозмінною групою по 6 букв. Обидва з цих двох типів стабілізаторів є максимальними підгрупами всієї групи автоморфізмів графа Гофмана — Синглтона.

Характеристичний поліном графа Гофмана — Синглтона дорівнює ${\displaystyle (x-7)(x-2)^{28}(x+3)^{21}}$. Тому граф Гофмана — Синглтона є інтегральним графом: його спектр повністю складається з цілих чисел.

Використовуючи тільки той факт, що граф Гофмана — Синглтона є сильно регулярним графом із параметрами (50,7,0,1), можна показати, що існує 1260 5-циклів, що містяться у графі Гофмана — Синглтона.

Крім того, граф Гофмана — Синглтона містить 525 копій графа Петерсена. Видалення будь-якого одного з них залишає копію унікальної (6,5)-клітки.^[7]

• Задача степеня — діаметра
• Таблиця найбільших відомих графів заданого діаметра і максимального степеня^[en]
• Граф Гофмана

• Benson, C. T.; Losey, N. E. (1971), On a graph of Hoffman and Singleton, Journal of Combinatorial Theory. Series B, 11 (1): 67—79, doi:10.1016/0095-8956(71)90015-3, ISSN 0095-8956, MR 0281658
• Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, с. 186 and 190, ISBN 0-521-43594-3.