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

Граф Хигмана — Симса
Рисунок, основанный на построении Поля Р. Хафнера [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].

Примечания

1. Hafner, 2004, с. R77(1–32).
2. Weisstein, Eric W. Higman–Sims Graph (англ.) на сайте Wolfram MathWorld.
3. Mesner, 1956.
4. Higman, Sims, 1968, с. 110–113.
5. Brouwer, Andries E. Higman–Sims graph  (неопр.). Дата обращения: 17 июня 2018. Архивировано 14 октября 2017 года.
6. Brouwer, Haemers, 1993, с. 397-407.
7. Conway, Sloane, 1998, с. 292=293.

Литература

• Hafner P. R. On the Graphs of Hoffman–Singleton and Higman–Sims // the Electronic Journal of Combinatorics. — 2004. — Т. 11, вып. 1. — С. R77(1–32).
• Dale Marsh Mesner. An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types. — Department of Statistics, Michigan State University, 1956. — (Doctoral Thesis).
• Donald G. Higman, Charles C. Sims. A simple group of order 44,352,000 // Mathematische Zeitschrift. — 1968. — Т. 105, вып. 2. — С. 110–113. — doi:10.1007/BF01110435.
• Brouwer A. E., Haemers W. H. The Gewirtz Graph: An Exercise in the Theory of Graph Spectra // Euro. J. Combin. — 1993. — Вып. 14.
• John H. Conway, Neil J. A. Sloane. chapter 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin groups") // Sphere Packings, Lattices and Groups. — 3rd. — Springer-Verlag, 1998. — (Grundlehren der mathematischen Wissenschaften). — ISBN 0-387-98585-9. — ISBN 1-4419-3134-1.