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

Граф Хигмана – Симса
Граф Хигмана – Симса
	Рисунок основан на конструкции Пола Р. Хафнера.
Назван в честь	Дональд Дж. Хигман ; Чарльз С. Симс
Вершины	100
Края	1100
Радиус	2
Диаметр	2
Обхват	4
Автоморфизм	88 704 000 ( ГС :2)
Характеристики	Сильно регулярный ; Край-транзитивный ; гамильтониан ; Эйлеров
	Таблица графиков и параметров

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

Строительство

Из графика 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 другими). Соедините строки друг с другом, если у них ровно один общий элемент (таких соседей 4x4 = 16). Полученный граф представляет собой граф Хигмана – Симса. Ряды соединены с 16 другими рядами и с 6 конструкциями == степень 22. Рисунки соединены с 14 рядами и 8 непересекающимися конструкциями == степень 22. Таким образом, все 100 вершин имеют степень 22 каждая.

Алгебраические свойства

Группа автоморфизмов графа Хигмана–Симса — это группа порядка 88 704 000, изоморфная полупрямому произведению группы Хигмана–Симса порядка 44 352 000 с циклической группой порядка 2. ^{[ 5 ]} Он имеет автоморфизмы, которые переводят любое ребро в любое другое ребро, что делает граф Хигмана-Симса реберно-транзитивным графом . ^{[ 6 ]} Внешние элементы вызывают нечетные перестановки на графе. Как упоминалось выше , существует 352 способа разбить граф Хигмана–Симса на пару графов Хоффмана–Синглтона; эти разделы фактически состоят из двух орбит размером 176 каждая, и внешние элементы группы Хигмана – Симса меняют местами эти орбиты. ^{[ 7 ]}

Характеристический полином графа Хигмана – Симса равен ( x - 22) ( x - 2) ⁷⁷( х + 8) ²². Следовательно, граф Хигмана–Симса является целым графом : его спектр полностью состоит из целых чисел. Это также единственный граф с этим характеристическим полиномом, что делает его графом, определяемым его спектром.

Внутри решетки Лича

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

Ссылки

^ Хафнер, PR (2004). «О графиках Хоффмана-Синглтона и Хигмана-Симса» (PDF) . Электронный журнал комбинаторики . 11 (1): R77 (1–32). дои : 10.37236/1830 . .
^ Вайсштейн, Эрик В. «График Хигмана – Симса» . Математический мир .
^ Меснер, Дейл Марш (1956). Исследование некоторых комбинаторных свойств частично сбалансированных неполных блочных экспериментальных планов и схем связей с детальным изучением планов латинского квадрата и родственных ему типов (Докторская диссертация). Статистический факультет Мичиганского государственного университета. МР 2612633 .
^ Хигман, Дональд Г.; Симс, Чарльз К. (1968). «Простая группа порядка 44 352 000» (PDF) . Математический журнал . 105 (2): 110–113. дои : 10.1007/BF01110435 . hdl : 2027.42/46258 . S2CID 32803979 . .
^ Брауэр, Андриес Э. «График Хигмана – Симса» .
^ Брауэр, А.Э. и Хемерс, WH «Граф Гевирца: упражнение в теории спектров графов». Евро. Дж. Комбин. 14, 397–407, 1993.
^ Конвей, Дж. Х. ; Кертис, RT; Нортон, СП ; Паркер, РА ; Уилсон, Р.А. (1985). Атлас конечных групп: максимальные подгруппы и обыкновенные характеры простых групп . при вычислительной помощи Дж. Г. Текрея. Издательство Оксфордского университета. ISBN 978-019853199-9 .
^ Конвей, Джон Х .; Слоан, Нил Дж. А. (декабрь 2010 г.). Сферические упаковки, решетки и группы . Основные принципы математических наук (3-е изд.). Издательство Спрингер . ISBN 978-1-4419-3134-4 . глава 10 (Джон Х. Конвей, «Три лекции об исключительных группах»), §3.5 («Группы Хигмана – Симса и Маклафлина»), стр. 292–293.

[1] Хафнер, PR (2004). «О графиках Хоффмана-Синглтона и Хигмана-Симса» (PDF) . Электронный журнал комбинаторики . 11 (1): R77 (1–32). дои : 10.37236/1830 . .

[2] Вайсштейн, Эрик В. «График Хигмана – Симса» . Математический мир .

[3] Меснер, Дейл Марш (1956). Исследование некоторых комбинаторных свойств частично сбалансированных неполных блочных экспериментальных планов и схем связей с детальным изучением планов латинского квадрата и родственных ему типов (Докторская диссертация). Статистический факультет Мичиганского государственного университета. МР 2612633 .

[4] Хигман, Дональд Г.; Симс, Чарльз К. (1968). «Простая группа порядка 44 352 000» (PDF) . Математический журнал . 105 (2): 110–113. дои : 10.1007/BF01110435 . hdl : 2027.42/46258 . S2CID 32803979 . .

[5] Брауэр, Андриес Э. «График Хигмана – Симса» .

[6] Брауэр, А.Э. и Хемерс, WH «Граф Гевирца: упражнение в теории спектров графов». Евро. Дж. Комбин. 14, 397–407, 1993.

[7] Конвей, Дж. Х. ; Кертис, RT; Нортон, СП ; Паркер, РА ; Уилсон, Р.А. (1985). Атлас конечных групп: максимальные подгруппы и обыкновенные характеры простых групп . при вычислительной помощи Дж. Г. Текрея. Издательство Оксфордского университета. ISBN 978-019853199-9 .

[8] Конвей, Джон Х .; Слоан, Нил Дж. А. (декабрь 2010 г.). Сферические упаковки, решетки и группы . Основные принципы математических наук (3-е изд.). Издательство Спрингер . ISBN 978-1-4419-3134-4 . глава 10 (Джон Х. Конвей, «Три лекции об исключительных группах»), §3.5 («Группы Хигмана – Симса и Маклафлина»), стр. 292–293.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]