Граф Гіґмана — Сімса
Граф Гіґмана — Сімса — це 22-регулярний неорієнтований граф зі 100 вершинами і 1100 ребрами. Граф є унікальним сильно регулярним графом srg(100,22,0,6), тобто, ніяка сусідня пара вершин не має спільних сусідів і будь-яка несусідня пара вершин має шість спільних сусідів. Граф уперше побудував МеснерШаблон:Sfn і перевідкрили 1968 року Шаблон:Нп і Шаблон:Нп як шлях визначення Шаблон:Не перекладено і ця група є підгрупою з індексом два в групі автоморфізмів графа Гіґмана — СімсаШаблон:Sfn.
Побудова починається з графа 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[1]. Граф має автоморфізми, що переводять будь-яке ребро в будь-яке інше ребро, що робить граф Гіґмана — Сімса реберно-транзитивнимШаблон:Sfn.
Характеристичним многочленом графа Гіґмана — Сімса є . Таким чином, граф Гіґмана — Сімса є цілим графом — його спектр складається виключно з цілих чисел. Граф є також єдиним графом з таким характеристичним многочленом, тому граф повністю визначається своїм спектром.
Всередині ґратки Ліча
Граф Гіґмана — Сімса в природний спосіб Шаблон:Не перекладено всередині ґратки Ліча — якщо X, Y і Z — три точки в ґратці Ліча, такі, що відстані XY, XZ і YZ рівні відповідно, то існує рівно 100 точок T ґратки Ліча, таких, що всі відстані XT, YT і ZT рівні 2, і якщо ми з'єднаємо дві такі точки T і T′, коли відстань між ними дорівнює , отриманий граф буде ізоморфним графу Гіґмана — Сімса. Більш того, множина всіх автоморфізмів ґратки Ліча (тобто рухів евклідового простору, що зберігають її), що зберігають точки X, Y і Z, є групою Гіґмана — Сімса (якщо ми дозволимо обмін X і Y, отримаємо розширення всіх автоморфізмів графа порядку 2). Це показує, що група Гіґмана — Сімса виявляється всередині груп Конвея Co2 (з розширенням порядку 2) і Co3, а отже, також усередині групи Co1Шаблон:Sfn.