В математической теории графов , то граф Хигман-Sims является 22- регулярного неориентированного графа с 100 вершин и 1100 кромок. Это уникальный сильно регулярный граф srg (100,22,0,6), в котором никакая соседняя пара вершин не имеет общего соседа, а каждая несоседняя пара вершин имеет шесть общих соседей. [2] Она была впервые построена Меснером (1956) и переоткрыта в 1968 году Дональдом Г. Хигманом и Чарльзом Симсом как способ определения группы Хигмена – Симса , подгруппы индекса два в группе автоморфизмов группы Хигмана. –Симс-график. [3]
График Хигмана – Симса | |
---|---|
Названный в честь | Дональд Г. Хигман Чарльз С. Симс |
Вершины | 100 |
Края | 1100 |
Радиус | 2 |
Диаметр | 2 |
Обхват | 4 |
Автоморфизмы | 88 704 000 ( HS : 2) |
Характеристики | Сильно регулярный Edge-транзитивный гамильтониан эйлеров |
Таблица графиков и параметров |
Строительство
Из графика M22
Возьмем граф M22 , сильно регулярный граф srg (77,16,0,4) и дополним его 22 новыми вершинами, соответствующими точкам S (3,6,22), каждый блок соединен со своими точками, и один дополнительная вершина C соединена с 22 точками.
Из графика Хоффмана – Синглтона
В графе Хоффмана – Синглтона имеется 100 независимых наборов размера 15 . Создайте новый граф со 100 соответствующими вершинами и соедините вершины, соответствующие независимые множества которых имеют ровно 0 или 8 общих элементов. Полученный граф Хигмана – Симса можно разделить на две копии графа Хоффмана – Синглтона 352 способами.
Из куба
Возьмите куб с вершинами, обозначенными 000, 001, 010, ..., 111. Возьмите все 70 возможных 4-х наборов вершин и оставьте только те, для которых XOR оценивается как 000; таких 4-множеств 14, соответствующих 6 граням + 6 диагональных прямоугольниках + 2 тетраэдрам четности. Это 3- (8,4,1) блочная конструкция по 8 точкам, с 14 блоками размером 4 блока, каждая точка появляется в 7 блоках, каждая пара точек появляется 3 раза, каждая тройка точек встречается ровно один раз. Переставьте исходные 8 вершин в любую из 8! = 40320 способов и отбросьте дубликаты. Затем существует 30 различных способов переименовать вершины (т. Е. 30 различных схем, которые изоморфны друг другу путем перестановки точек). Это потому, что существует 1344 автоморфизма , а 40320/1344 = 30.
Создайте вершину для каждого из 30 дизайнов и для каждой строки каждого дизайна (всего таких строк 70, каждая строка представляет собой 4 набора из 8 и появляется в 6 дизайнах). Соедините каждую конструкцию с ее 14 рядами. Соединяйте непересекающиеся дизайны друг с другом (каждый дизайн не пересекается с 8 другими). Соединяйте строки между собой, если у них ровно один общий элемент (таких соседей 4х4 = 16). В результате получается граф Хигмана – Симса. Строки соединены с 16 другими рядами и с 6 конструкциями == степень 22. Конструкции соединены с 14 рядами и 8 непересекающимися конструкциями == степень 22. Таким образом, все 100 вершин имеют степень 22 каждая.
Алгебраические свойства
Группа автоморфизмов графа Хигман-Sims является группой порядка 88,704,000 изоморфна полупрямый продукт из группы Хигмана-Sims порядка 44,352,000 с циклической группой порядка 2. [4] Он имеет автоморфизмы , которые принимают любую кромку к любому другому ребро, что делает граф Хигмана – Симса реберно-транзитивным графом . [5]
Характеристический многочлен графа Хигмана – Симса равен ( x - 22) ( x - 2) 77 ( x + 8) 22 . Следовательно, граф Хигмана – Симса является интегральным графом : его спектр полностью состоит из целых чисел. Это также единственный граф с этим характеристическим многочленом, что делает его графом, определяемым его спектром.
Внутри решетки пиявки
Граф Хигмана – Симса естественным образом возникает внутри решетки Пиявки : если X , Y и Z - три точки в решетке Пиявки такие, что расстояния XY , XZ и YZ равнысоответственно, то имеется ровно 100 точек T решетки пиявки таких, что все расстояния XT , YT и ZT равны 2, и если мы соединим две такие точки T и T ′, когда расстояние между ними равно, полученный граф изоморфен графу Хигмана – Симса. Кроме того, множество всех автоморфизмов решетки Лича (то есть евклидовых конгруэнций, фиксирующих ее), фиксирующих каждое из X , Y и Z, является группой Хигмана – Симса (если мы позволим поменять местами X и Y , расширение порядка 2 всех графовых автоморфизмов). Это показывает, что группа Хигмана – Симса находится внутри групп Конвея Co 2 (с его расширением порядка 2) и Co 3 , а следовательно, и Co 1 . [6]
Рекомендации
- Перейти ↑ Hafner, PR (2004). «О графах Хоффмана – Синглтона и Хигмана – Симса» (PDF) . Электронный журнал комбинаторики . 11 (1): R77 (1–32). DOI : 10.37236 / 1830 . Внешняя ссылка в
|journal=
( помощь ) . - ^ Вайсштейн, Эрик В. "График Хигмана – Симса" . MathWorld .
- ^ Higman, Donald G .; Симс, Чарльз К. (1968). «Простая группа порядка 44,352,000» (PDF) . Mathematische Zeitschrift . 105 (2): 110–113. DOI : 10.1007 / BF01110435 . ЛВП : 2027,42 / 46258 ..
- ^ Брауэр, Андрис Э. «Граф Хигмана – Симса» .
- ^ Брауэр, АЯ и Haemers, WH «Гевиртца Graph: Упражнение в теории графов Spectra.» Евро. J. Combin. 14, 397–407, 1993.
- ^ Конвей, Джон Х .; Слоан, Нил Дж. Сферические упаковки, решетки и группы . Grundlehren der Mathematischen Wissenschaften (3-е изд.). Springer-Verlag . ISBN 1-4419-3134-1. глава 10 (Джон Х. Конвей, «Три лекции об исключительных группах»), §3.5 («Группы Хигмена – Симса и Маклафлина»), стр. 292–293.
- Меснер, Дейл Марш (1956), Исследование некоторых комбинаторных свойств частично сбалансированных неполных блочных экспериментальных планов и ассоциативных схем с подробным изучением планов латинского квадрата и родственных типов , докторская диссертация, Департамент статистики, Мичиганский государственный университет, MR 2612633