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

Граф Хоффмана — Синглтона. Подграф с синими рёбрами является суммой десяти непересекающихся пентагонов.

Граф Хоффмана — Синглтона — 7-однородный неориентированный граф с 50 вершинами и 175 рёбрами. Граф является единственным сильно регулярным графом с параметрами $(50,7,0,1)$Шаблон:Sfn. Граф был построен Аланом Хоффманом и Робертом Синглтоном, когда они пытались классифицировать все графы Мура, и он является графом Мура с наибольшим порядком, для которого известно, что такой граф существуетШаблон:Sfn. Поскольку граф является графом Мура, в котором каждая вершина имеет степень 7, а обхват графа равен 5, граф является клеткой $(7,5)$.

Построение

Существует много путей построения графов Хоффмана — Синглтона.

Построение на основе пятиугольников и пентаграмм

Возьмём 5 пятиугольников $P_h$ и 5 пентаграмм $Q_i$ так, что вершина $j$ пятиугольника $P_h$ смежна вершинам $j-1$ и $j+1$ пятиугольника $P_h$ и вершина $j$ пентаграммы $Q_i$ смежна вершинам $j-2$ и $j+2$ пентаграммы $Q_i$. Свяжем вершину $j$ графа $P_h$ с вершиной $h\bullet i+j$ графа $Q_i$. (Все индексы берутся по модулю 5.)

Построение из троек и плоскостей Фано

Возьмём плоскость Фано и рассмотрим переставки её 7 точек, чтобы получить 30 плоскостей Фано. Выберем одну из этих плоскостей. Имеется 14 других плоскостей Фано, имеющих в точности одну общую тройку («прямую») с выбранной плоскостью. Возьмём эти 15 плоскостей Фано и отбросим оставшиеся 15. Рассмотрим ⁷C₃ = 35 троек из 7 чисел. Теперь соединим (ребром) тройку с плоскостями Фано, содержащими эту тройку, а также соединим непересекающиеся тройки друг с другом. Получившийся граф является графом Хоффмана — Синглтона, он состоит из 50 вершин, соответствующих 35 тройкам и 15 плоскостям Фано, и каждая вершина имеет степень 7. Вершины, соответствующие плоскостям Фано, соединены с 7 тройками по определению, поскольку плоскость Фано имеет 7 прямых. Каждая тройка связана с 3 различными плоскостями Фано, включающими её, и с 4 другими тройками, с которыми она не пересекается.

Алгебраические свойства

Группа автоморфизмов графа Хоффмана — Синглтона является группой порядка 252000 и изоморфна PΣU(3,5²), полупрямому произведению Шаблон:Нп3 $PSU(3,5^2)$ и циклической группы порядка 2, сгенерировнной эндоморфизмом Фробениуса. Автоморфизм действует транзитивно на вершины и рёбра графа. Таким образом, граф Хоффмана — Синглтона является симметричным графом. Стабилизатор вершин графа изоморфен симметрической группе $S_7$ на 7 буквах. Стабилизатор множества рёбер изоморфен $Aut(A_6)=A_6\cdot 2^2$, где $A_6$ — знакопеременная группа на 6 буквах. Оба типа стабилизаторов являются максимальными подгруппами полной группы автоморфизмов графа Хоффмана — Синглтона.

Характеристический многочлен графа Хоффмана — Синглтона равен $(x-7)(x-2{)}^{28}(x+3{)}^{21}$. Таким образом, граф Хоффмана — Синглтона является целочисленным — его спектр состоит полностью из целых чисел.

Подграфы

Используя только факт, что граф Хоффмана — Синглтона является строго регулярным с параметрами $(50,7,0,1)$, можно показать, что в нём существует 1260 циклов длины 5.

Кроме того, граф Хоффмана — Синглтона содержит 525 копий графа Петерсена. Удаление одного из них даёт копию единственной $(6,5)$-клеткиШаблон:Sfn.

См. также

• Шаблон:Нп3

Литература

• Шаблон:Статья
• Шаблон:Cite webШаблон:Недоступная ссылка
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга.
• Шаблон:Cite web
• Шаблон:Статья
• Шаблон:Статья