
 Окремі частини побудови Гафнера.
Граф Гіґмана — Сімса — це 22-регулярний неорієнтований граф зі 100 вершинами і 1100 ребрами. Граф є унікальним сильно регулярним графом srg(100,22,0,6), тобто, ніяка сусідня пара вершин не має спільних сусідів і будь-яка несусідня пара вершин має шість спільних сусідів. Граф уперше побудував Меснер і перевідкрили 1968 року  і  як шлях визначення  і ця група є підгрупою з індексом два в групі автоморфізмів графа Гіґмана — Сімса.

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

Граф Гіґмана — Сімса формується додаванням 22 точок W22 і 100-ї вершини C. Сусідами вершини C є ці 22 точки. Точка суміжна блоку тоді й лише тоді, коли вона належить блоку.

Граф Гіґмана — Сімса можна розбити на дві копії графа Гофмана — Сінглтона 352 способами.

Алгебричні властивості
Група автоморфізмів графа Гіґмана — Сімса є групою порядку 88 704 000, ізоморфною напівпрямому добутку  порядку 44 352 000 на циклічну групу порядку 2. Граф має автоморфізми, що переводять будь-яке ребро в будь-яке інше ребро, що робить граф Гіґмана — Сімса реберно-транзитивним.

Характеристичним многочленом графа Гіґмана — Сімса є . Таким чином, граф Гіґмана — Сімса є цілим графом — його спектр складається виключно з цілих чисел. Граф є також єдиним графом з таким характеристичним многочленом, тому граф повністю визначається своїм спектром.

Всередині ґратки Ліча
 Проєкція графа Гіґмана — Сімса в ґратку Ліча.
Граф Гіґмана — Сімса в природний спосіб  всередині решітки Ліча — якщо X, Y і Z — три точки в ґратці Ліча, такі, що відстані XY, XZ і YZ рівні  відповідно, то існує рівно 100 точок T ґратки Ліча, таких, що всі відстані XT, YT і ZT рівні 2, і якщо ми з'єднаємо дві такі точки T і T′, коли відстань між ними дорівнює , отриманий граф буде ізоморфним графу Гіґмана — Сімса. Більш того, множина всіх автоморфізмів ґратки Ліча (тобто рухів евклідового простору, що зберігають її), що зберігають точки X, Y і Z, є групою Гіґмана — Сімса (якщо ми дозволимо обмін X і Y, отримаємо розширення всіх автоморфізмів графа порядку 2). Це показує, що група Гіґмана — Сімса виявляється всередині груп Конвея Co2 (з розширенням порядку 2) і Co3, а отже, також усередині групи Co1.

Див. також
* Граф Гевірца

Примітки


Література

* 
* 
* 
* 
* 



