Главная
Граф Хоффмана — Синглтона — 7-однородный неориентированный граф с 50 вершинами и 175 рёбрами. Граф является единственным сильно регулярным графом с параметрами ( 50 , 7 , 0 , 1 ) {displaystyle (50,7,0,1)} . Граф был построен Аланом Хоффманом и Робертом Синглтоном, когда они пытались классифицировать все графы Мура, и он является графом Мура с наибольшим порядком, для которого известно, что такой граф существует. Поскольку граф является графом Мура, в котором каждая вершина имеет степень 7, а обхват графа равен 5, граф является клеткой ( 7 , 5 ) {displaystyle (7,5)} .
Построение
Существует много путей построения графов Хоффмана — Синглтона.
Построение на основе пятиугольников и пентаграмм
Возьмём 5 пятиугольников P h {displaystyle P_{h}} и 5 пентаграмм Q i {displaystyle Q_{i}} так, что вершина j {displaystyle j} пятиугольника P h {displaystyle P_{h}} смежна вершинам j − 1 {displaystyle j-1} и j + 1 {displaystyle j+1} пятиугольника P h {displaystyle P_{h}} и вершина j {displaystyle j} пентаграммы Q i {displaystyle Q_{i}} смежна вершинам j − 2 {displaystyle j-2} и j + 2 {displaystyle j+2} пентаграммы Q i {displaystyle Q_{i}} . Свяжем вершину j {displaystyle j} графа P h {displaystyle P_{h}} с вершиной h ∙ i + j {displaystyle hullet {i}+j} графа Q i {displaystyle Q_{i}} . (Все индексы берутся по модулю 5.)
Построение из троек и плоскостей Фано
Возьмём плоскость Фано и рассмотрим переставки её 7 точек, чтобы получить 30 плоскостей Фано. Выберем одну из этих плоскостей. Имеется 14 других плоскостей Фано, имеющих в точности одну общую тройку («прямую») с выбранной плоскостью. Возьмём эти 15 плоскостей Фано и отбросим оставшиеся 15. Рассмотрим 7C3 = 35 троек из 7 чисел. Теперь соединим (ребром) тройку с плоскостями Фано, содержащими эту тройку, а также соединим непересекающиеся тройки друг с другом. Получившийся граф является графом Хоффмана — Синглтона, он состоит из 50 вершин, соответствующих 35 тройкам и 15 плоскостям Фано, и каждая вершина имеет степень 7. Вершины, соответствующие плоскостям Фано, соединены с 7 тройками по определению, поскольку плоскость Фано имеет 7 прямых. Каждая тройка связана с 3 различными плоскостями Фано, включающими её, и с 4 другими тройками, с которыми она не пересекается.
Алгебраические свойства
Группа автоморфизмов графа Хоффмана — Синглтона является группой порядка 252000 и изоморфна PΣU(3,52), полупрямому произведению проективной специальной унитарной группы P S U ( 3 , 5 2 ) {displaystyle PSU(3,5^{2})} и циклической группы порядка 2, сгенерировнной эндоморфизмом Фробениуса. Автоморфизм действует транзитивно на вершины и рёбра графа. Таким образом, граф Хоффмана — Синглтона является симметричным графом. Стабилизатор вершин графа изоморфен симметрической группе S 7 {displaystyle S_{7}} на 7 буквах. Стабилизатор множества рёбер изоморфен A u t ( A 6 ) = A 6 ⋅ 2 2 {displaystyle Aut(A_{6})=A_{6}cdot 2^{2}} , где A 6 {displaystyle A_{6}} — знакопеременная группа на 6 буквах. Оба типа стабилизаторов являются максимальными подгруппами полной группы автоморфизмов графа Хоффмана — Синглтона.
Характеристический многочлен графа Хоффмана — Синглтона равен ( x − 7 ) ( x − 2 ) 28 ( x + 3 ) 21 {displaystyle (x-7)(x-2)^{28}(x+3)^{21}} . Таким образом, граф Хоффмана — Синглтона является целочисленным — его спектр состоит полностью из целых чисел.
Подграфы
Используя только факт, что граф Хоффмана — Синглтона является строго регулярным с параметрами ( 50 , 7 , 0 , 1 ) {displaystyle (50,7,0,1)} , можно показать, что в нём существует 1260 циклов длины 5.
Кроме того, граф Хоффмана — Синглтона содержит 525 копий графа Петерсена. Удаление одного из них даёт копию единственной ( 6 , 5 ) {displaystyle (6,5)} -клетки.