Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В математической теории графов граф Хигмана — Симса — это 22-регулярный неориентированный граф со 100 вершинами и 1100 ребрами. Это единственный сильно регулярный граф srg(100, 22, 0, 6), в котором никакая пара соседних вершин не имеет общего соседа, а каждая пара несоседних вершин имеет шесть общих соседей. Он был впервые построен и повторно открыт в 1968 году Дональдом Г. Хигманом и Чарльзом С. Симсом как способ определения группы Хигмана — Симса, подгруппы индекса два в группе автоморфизмов графа Хоффмана — Синглтона.
In mathematical graph theory, the Higman–Sims graph is a 22 regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and each non neighboring pair of vertices share six common neighbors. It was first constructed by and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, a subgroup of index two in the group of automorphisms of the Hoffman–Singleton graph.
Из графика M22
Возьмем граф M22, сильно регулярный граф srg(77,16,0,4) и расширим его, добавив 22 новые вершины, соответствующие точкам S(3,6,22), причем каждый блок соединен со своими точками, и одну дополнительную вершину C, соединенную с этими 22 точками.
Take the M22 graph, a strongly regular graph srg(77,16,0,4) and augment it with 22 new vertices corresponding to the points of S(3,6,22), each block being connected to its points, and one additional vertex C connected to the 22 points.
Из графика Хоффмана-Синглтона
В графике Хоффмана — Синглтона содержится 100 независимых множеств размера 15. Постройте новый граф со 100 соответствующими вершинами и соедините вершины, независимые множества которых имеют ровно 0 или 8 общих элементов. Полученный граф Хигмана — Симса можно разбить на две копии графа Хоффмана — Синглтона 352 способами.
There are 100 independent sets of size 15 in the Hoffman–Singleton graph. Create a new graph with 100 corresponding vertices, and connect vertices whose corresponding independent sets have exactly 0 or 8 elements in common. The resulting Higman–Sims graph can be partitioned into two copies of the Hoffman–Singleton graph in 352 ways.
Из кубика
Возьмем куб с вершинами, обозначенными 000, 001, 010, 111. Возьмите все 70 возможных четверок вершин и оставьте только те, чей XOR равен 000; существует 14 таких четверок, соответствующих 6 граням + 6 диагональным прямоугольникам + 2 тетраэдрам четности. Это 3-(8,4,1) блок-схема на 8 точках, с 14 блоками размера 4, каждая точка входит в 7 блоков, каждая пара точек встречается 3 раза, а каждая тройка точек – ровно один раз. Переставьте исходные 8 вершин любым из 8! = 40320 способов и отбросьте дубликаты. Тогда существует 30 различных способов перемаркировки вершин (то есть 30 различных схем, все изоморфные друг другу перестановкой точек). Это связано с тем, что существует 1344 автоморфизмов, а 40320/1344 = 30. Создайте вершину для каждой из 30 схем и для каждой строки каждой схемы (всего таких строк 70, каждая строка представляет собой четверку из 8 и встречается в 6 схемах). Соедините каждую схему с ее 14 строками. Соедините несвязанные схемы друг с другом (каждая схема несвязанна с 8 другими). Соедините строки друг с другом, если у них ровно один общий элемент (существует 4x4 = 16 таких соседей). Полученный граф – это граф Хигмана-Симса. Строка соединена с 16 другими строками и 6 схемами, что дает степень 22. Схемы соединены с 14 строками и 8 несвязанными схемами, что дает степень 22. Таким образом, все 100 вершин имеют степень 22.
Take a cube with vertices labeled 000, 001, 010, , 111. Take all 70 possible 4 sets of vertices, and retain only the ones whose XOR evaluates to 000; there are 14 such 4 sets, corresponding to the 6 faces + 6 diagonal rectangles + 2 parity tetrahedra. This is a 3 (8,4,1) block design on 8 points, with 14 blocks of block size 4, each point appearing in 7 blocks, each pair of points appearing 3 times, each triplet of points occurring exactly once. Permute the original 8 vertices any of 8! = 40320 ways, and discard duplicates. There are then 30 different ways to relabel the vertices (i. e., 30 different designs that are all isomorphic to each other by permutation of the points). This is because there are 1344 automorphisms, and 40320/1344 = 30. Create a vertex for each of the 30 designs, and for each row of every design (there are 70 such rows in total, each row being a 4 set of 8 and appearing in 6 designs). Connect each design to its 14 rows. Connect disjoint designs to each other (each design is disjoint with 8 others). Connect rows to each other if they have exactly one element in common (there are 4x4 = 16 such neighbors). The resulting graph is the Higman–Sims graph. Rows are connected to 16 other rows and to 6 designs == degree 22. Designs are connected to 14 rows and 8 disjoint designs == degree 22. Thus all 100 vertices have degree 22 each.
Алгебраические свойства
Автоморфическая группа графа Хигмана — Симса — это группа порядка, изоморфная полупрямому произведению группы Хигмана — Симса порядка с циклической группой порядка 2. Она имеет автоморфизмы, переводящие любое ребро в любое другое ребро, что делает граф Хигмана — Симса ребро-транзитивным графом. Внешние элементы индуцируют нечётные перестановки на графе. Как упоминалось выше, существует 352 способа разбить граф Хигмана — Симса на пару графов Хоффмана — Синглтона; эти разбиения фактически образуют 2 орбиты размером 176 каждая, и внешние элементы группы Хигмана — Симса меняют эти орбиты местами. Характерный полином графа Хигмана — Симса равен (x − 22)(x − 2)⁷⁷(x + 8)²². Следовательно, граф Хигмана — Симса является интегральным графом: его спектр состоит исключительно из целых чисел. Он также является единственным графом с таким характерным полиномом, что делает его графом, определяемым своим спектром.
The automorphism group of the Higman–Sims graph is a group of order isomorphic to the semidirect product of the Higman–Sims group of order with the cyclic group of order 2. It has automorphisms that take any edge to any other edge, making the Higman–Sims graph an edge transitive graph. The outer elements induce odd permutations on the graph. As mentioned above, there are 352 ways to partition the Higman–Sims graph into a pair of Hoffman–Singleton graphs; these partitions actually come in 2 orbits of size 176 each, and the outer elements of the Higman–Sims group swap these orbits. The characteristic polynomial of the Higman–Sims graph is (x − 22)(x − 2)77(x + 8)22. Therefore, the Higman–Sims graph is an integral graph: its spectrum consists entirely of integers. It is also the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
Внутри решетки пиявки
Граф Хигмана — Симса естественным образом возникает внутри решетки Лича: если X, Y и Z — три точки в решетке Лича, такие, что расстояния XY, XZ и YZ соответственно равны, то существует ровно 100 точек решетки Лича T, таких, что все расстояния XT, YT и ZT равны 2, и если соединить две такие точки T и T′, когда расстояние между ними равно, то полученный граф изоморфен графу Хигмана — Симса. Более того, множество всех автоморфизмов решетки Лича (то есть евклидовых конгруэнций, сохраняющих её), фиксирующих каждую из точек X, Y и Z, является группой Хигмана — Симса (если допускать перестановку X и Y, то получается расширение порядка 2 всех автоморфизмов графа). Это показывает, что группа Хигмана — Симса содержится в группах Конвея Co2 (с расширением порядка 2) и Co3, а следовательно, и в Co1.
The Higman–Sims graph naturally occurs inside the Leech lattice: if X, Y and Z are three points in the Leech lattice such that the distances XY, XZ and YZ are respectively, then there are exactly 100 Leech lattice points T such that all the distances XT, YT and ZT are equal to 2, and if we connect two such points T and T′ when the distance between them is , the resulting graph is isomorphic to the Higman–Sims graph. Furthermore, the set of all automorphisms of the Leech lattice (that is, Euclidean congruences fixing it) which fix each of X, Y and Z is the Higman–Sims group (if we allow exchanging X and Y, the order 2 extension of all graph automorphisms is obtained). This shows that the Higman–Sims group occurs inside the Conway groups Co2 (with its order 2 extension) and Co3, and consequently also Co1.