Граф Хигмана — Симса

Граф Хигмана — Симса
Рисунок, основанный на построении Поля Р. Хафнера [1]
Назван в честь	Дональд Г Хигман Чарльз Симс
Вершин	100
Рёбер	1100
Радиус	2
Диаметр	2
Автоморфизмы	88 704 000 (HS:2)
Свойства	Сильно регулярный рёберно-транзитивный гамильтонов эйлеров
Медиафайлы на Викискладе

Граф Хигмана — Симса — это 22-регулярный неориентированный граф со 100 вершинами и 1100 рёбрами. Граф является уникальным сильно регулярным графом srg(100,22,0,6), т.е. никакая соседняя пара вершин не имеет общих соседей и любая несоседняя пара вершин имеет шесть общих соседей^[2]. Граф был впервые построен Меснером^[3] и был переоткрыт в 1968 Дональдом Дж. Хигманом и Чарльзом Симсом как путь определения группы Хигмана — Симса^[англ.] и эта группа является подгруппой с индексом два в группе автоморфизмов графа Хигмана — Симса^[4].

Построение начинается с графа M₂₂, 77 вершин которого являются блоками S(3,6,22) системы Штейнера W₂₂. Смежные вершины определяются как непересекающиеся блоки. Этот граф является сильно регулярным srg(77,16,0,4), т.е. любая вершина имеет 16 соседей, любые 2 смежные вершины не имеют общих соседей и любые 2 несмежные вершины имеют 4 общих соседа. Этот граф имеет M₂₂:2 в качестве группы автоморфизмов, где M₂₂ является группой Матьё.

Граф Хигмана — Симса формируется путём добавления 22 точек W₂₂ и 100-й вершины C. Соседи вершины C определяются как эти 22 точки. Точка смежна блоку тогда и только тогда, когда она принадлежит блоку.

Граф Хигмана — Симса можно разбить на две копии графа Хоффмана — Синглтона 352 способами.

Группа автоморфизмов графа Хигмана — Симса является группой порядка 88 704 000, изоморфной полупрямому произведению группы Хигмана — Симса^[англ.] порядка 44 352 000 на циклическую группу порядка 2^[5]. Граф имеет автоморфизмы, переводящие любое ребро в любое другое ребро, что делает граф Хигмана — Симса рёберно-транзитивным^[6].

Характеристическим многочленом графа Хигмана — Симса является ${\displaystyle (x-22)(x-2)^{77}(x+8)^{22}}$. Таким образом, граф Хигмана — Симса является целым графом — его спектр состоит исключительно из целых чисел. Граф является также единственным графом с таким характеристическим многочленом, так что граф полностью определяется своим спектром.

Граф Хигмана — Симса естественным образом размещается^[англ.] внутри решётки Лича — если X, Y и Z являются тремя точками в решётке Лича, такими, что расстояния XY, XZ и YZ равны ${\displaystyle 2,{\sqrt {6}},{\sqrt {6}}}$ соответственно, то существует в точности 100 точек T решётки Лича, таких, что все расстояния XT, YT и ZT равны 2, и если мы соединим две такие точки T и T′, когда расстояние между ними равно ${\displaystyle {\sqrt {6}}}$, получившийся граф будет изоморфен графу Хигмана — Симса. Более того, множество всех автоморфизмов решётки Лича (то есть движение евклидового пространства, сохраняющих её) сохраняющих точки X, Y и Z, является группой Хигмана — Симса (если мы позволим обмен X и Y, получим расширение всех автоморфизмов графа порадка 2). Это показывает, что группа Хигмана — Симса обнаруживается внутри групп Конвея Co₂ (с расширением порядка 2) и Co₃, а следовательно, также внутри группы Co₁^[7].