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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Граф Хигмана — Симса
Рисунок, основанный на построении Поля Р. Хафнера [1]
Рисунок, основанный на построении Поля Р. Хафнера [1]
Назван в честь Дональд Г Хигман
Чарльз Симс
Вершин 100
Рёбер 1100
Радиус 2
Диаметр 2
Автоморфизмы 88 704 000 (HS:2)
Свойства Сильно регулярный
рёберно-транзитивный
гамильтонов
эйлеров
Логотип Викисклада Медиафайлы на Викискладе
Отдельные части построения Хафнера.

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

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

Граф Хигмана — Симса формируется путём добавления 22 точек W22 и 100-й вершины C. Соседи вершины C определяются как эти 22 точки. Точка смежна блоку тогда и только тогда, когда она принадлежит блоку.


Граф Хигмана — Симса можно разбить на две копии графа Хоффмана — Синглтона 352 способами.

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

[править | править код]

Группа автоморфизмов графа Хигмана — Симса является группой порядка 88 704 000, изоморфной полупрямому произведению группы Хигмана — Симса[англ.] порядка 44 352 000 на циклическую группу порядка 2[5]. Граф имеет автоморфизмы, переводящие любое ребро в любое другое ребро, что делает граф Хигмана — Симса рёберно-транзитивным[6].

Характеристическим многочленом графа Хигмана — Симса является . Таким образом, граф Хигмана — Симса является целым графом — его спектр состоит исключительно из целых чисел. Граф является также единственным графом с таким характеристическим многочленом, так что граф полностью определяется своим спектром.

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

[править | править код]
Проекция графа Хигмана — Симса в решётку Лича.

Граф Хигмана — Симса естественным образом размещается[англ.] внутри решётки Лича — если X, Y и Z являются тремя точками в решётке Лича, такими, что расстояния XY, XZ и YZ равны соответственно, то существует в точности 100 точек T решётки Лича, таких, что все расстояния XT, YT и ZT равны 2, и если мы соединим две такие точки T и T′, когда расстояние между ними равно , получившийся граф будет изоморфен графу Хигмана — Симса. Более того, множество всех автоморфизмов решётки Лича (то есть движение евклидового пространства, сохраняющих её) сохраняющих точки X, Y и Z, является группой Хигмана — Симса (если мы позволим обмен X и Y, получим расширение всех автоморфизмов графа порадка 2). Это показывает, что группа Хигмана — Симса обнаруживается внутри групп Конвея Co2 (с расширением порядка 2) и Co3, а следовательно, также внутри группы Co1[7].

Примечания

[править | править код]
  1. Hafner, 2004, с. R77(1–32).
  2. Weisstein, Eric W. Higman–Sims Graph (англ.) на сайте Wolfram MathWorld.
  3. Mesner, 1956.
  4. Higman, Sims, 1968, с. 110–113.
  5. Brouwer, Andries E. Higman–Sims graph. Дата обращения: 17 июня 2018. Архивировано 14 октября 2017 года.
  6. Brouwer, Haemers, 1993, с. 397-407.
  7. Conway, Sloane, 1998, с. 292=293.

Литература

[править | править код]
  • Hafner P. R. On the Graphs of Hoffman–Singleton and Higman–Sims // the Electronic Journal of Combinatorics. — 2004. — Т. 11, вып. 1. — С. R77(1–32).
  • Dale Marsh Mesner. An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types. — Department of Statistics, Michigan State University, 1956. — (Doctoral Thesis).
  • Donald G. Higman, Charles C. Sims. A simple group of order 44,352,000 // Mathematische Zeitschrift. — 1968. — Т. 105, вып. 2. — С. 110–113. — doi:10.1007/BF01110435.
  • Brouwer A. E., Haemers W. H. The Gewirtz Graph: An Exercise in the Theory of Graph Spectra // Euro. J. Combin. — 1993. — Вып. 14.
  • John H. Conway, Neil J. A. Sloane. chapter 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin groups") // Sphere Packings, Lattices and Groups. — 3rd. — Springer-Verlag, 1998. — (Grundlehren der mathematischen Wissenschaften). — ISBN 0-387-98585-9. — ISBN 1-4419-3134-1.