Введение к работе
Актуальность темы. Диссертационная работа посвящена изучению некоторых, представляющих интерес, комбинаторно-алгебраических свойств конечных примитивных групп подстановок и вершинно-примитивных графов. В ней исследуются минимальные асимметрические разбиения для конечных примитивных групп подстановок и различительные числа для вершинно-примитивных графов. Кроме того, в связи с одним вопросом П. Камерона исследуются конечные примитивные группы подстановок со стабилизатором двух точек, нормальным в стабилизаторе одной из них.
В работе П. Камерона, П. Ноймана и Я. Саксла1 доказано, что (с точностью до подстановочного изоморфизма) существует лишь конечное число примитивных групп подстановок G на конечных множествах X таких, что Alt(X) ^ G и глобальный стабилизатор любого подмножества R множества X в группе G нетривиален (т.е. С^щ ф 1). Позднее, в работе А. Сереша2, было получено описание примитивных групп подстановок G на конечных множествах X таких, что Сгд} ф 1 для любого ЙСІ. При этом остался открытым вопрос построения множеств с тривиальными глобальными стабилизаторами в случаях, когда такие множества существуют. В связи с этим актуальным является явное указание таких множеств. В диссертации указанный вопрос решен для конечных не почти простых примитивных групп подстановок.
Пусть G — группа подстановок на конечном множестве X. Различительным числом (distinguishing number3) D{G) группы G называется минимальное натуральное число п, для которого существует функция X ' X —> {1, ..., п} такая, что из условий д Є G и х(я(х)) = х(х) для всех х Є X следует д = 1. Разбиение 7Г = {Xi, ...,} множества X будем называть асимметрическим, если из д Є G и д(Х{) = Хі для всех 1 < і < к следует д = 1. Минимальным, асимметрическим разбиением множества X будем называть асимметрическое разбиение мощности D(G).
1Cameron P.J., Neumann P.M., Saxl J. On groups with no regular orbits on the set of subsets // Arch. Math. 1984. Vol. 43. P. 295-296.
2Seress A. Primitive groups with no regular orbits on the sets of subsets// Bull. London. Math. Soc. 1997. Vol. 29. P. 697-704.
3Tymoczko J. Distinguishing numbers for graphs and groups //Electron. J. Combin. 2004. Vol. 11. #R63.
Для неединичной группы подстановок G на конечном множестве X справедливость равенства D{G) = 2 эквивалентна существованию подмножества R множества X со свойством С^щ = 1. Таким образом, результат А. Сереша2 дает описание класса конечных примитивных групп подстановок G с D{G) > 3. В диссертации завершается нахождение значений D{G) для всех конечных примитивных групп подстановок G.
Пусть Г — конечный неориентированный граф без петель и кратных ребер, V(V) — множество вершин графа Г. Положим D(T) = D(Aut(T)) (Aut(r) рассматривается как группа подстановок на множестве V(Г)). Значения D(T) для отдельных графов были получены, например, в работах М. Альбертсона и К. Коллинза4, Дж. Тимошко5 и К. Коллинза и А. Тренка6. В связи с этим актуальным является получение значений D(T) для всех конечных графов Г с вершинно-примитивной группой автоморфизмов. Эти значения получены в диссертации.
Глава 3 диссертации посвящена следующему вопросу П. Камерона (см. П. Камерон7 и вопрос 9.69 из Коуровской тетради8). Пусть G — примитивная группа подстановок на конечном множестве X, х Є X, у Є X \ {х} и Gx действует регулярно на орбите Gx(y) (т.е. индуцирует на Gx(y) регулярную группу подстановок). Верно ли, что это действие точное, т.е., что \GX\ = \Gx(y)\?
Можно показать, что регулярность действия группы Gx на Gx(y) эквивалентна свойству Gx^y
(Рг) если х Є X, у Є X \ {ж}, то Gx,y Gx влечет Gx,y = 1.
Очевидно, вопрос П. Камерона эквивалентен также естественному вопросу о выполнении для произвольной абстрактной конечной группы G
4Albertson М.О., Collins K.L. Symmetry breaking in graphs // Electron. J. Combin. 1996. Vol. 3. #R18.
5Tymoczko J. Distinguishing numbers for graphs and groups //Electron. J. Combin. 2004. Vol. 11. #R63.
6Collins K. L., Trenk A. N. The distinguishing chromatic number //Electron. J. Combin. 2006. Vol. 13. #R16.
7Camerom P.J. Suborbits in transitive permutation groups // In "Combinatorics"(M. Hall, Jr. and J. H. van Lint, eds), Math. Centrum, Amsterdam, 1975, P. 419-450.
8Коуровская тетрадь. Нерешенные вопросы теории групп. Изд. 15. Новосибирск: Новосиб. гос. ун-т., 2002.
следующего свойства:
(Рг*) если М\ и М^ — различные сопряженные максимальные подгруппы группы G, то Mi П М2 < Mi влечет М: П М2 < G.
Вопрос о точности действия стабилизатора Gx на регулярной подорби-те Gx(y) изучался давно. В отдельных частных случаях положительный ответ был получен в работах Г. Ритца9, М. Вейса10и Г. Виландта11. Заметим, что для транзитивной группы подстановок ответ на аналогичный вопрос, вообще говоря, отрицательный.
В связи с полученными классификацией конечных простых групп и результатами о максимальных подгруппах конечных простых групп представляет интерес их использование для исследования вопроса П. Камерона, предпринятое в диссертации.
Целью работы является
a) построение минимальных асимметрических разбиений для конеч
ных примитивных групп подстановок;
b) нахождение различительных чисел для конечных примитив
ных групп подстановок и конечных графов, допускающих вершинно-
примитивную группу автоморфизмов;
c) исследование, в связи с вопросом П. Камерона, конечных прими
тивных групп подстановок со стабилизатором двух точек, нормальным
в стабилизаторе одной из них.
Методы исследования. Основными методами исследования являются методы абстрактной теории групп и теории групп подстановок. Вместе с тем, используется компьютерная система GAP12.
Научная новизна. Все основные результаты диссертации являются новыми.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории групп, теории графов, комбинаторике и их приложениях.
9Reitz H.L. On primitive groups of odd order // Amer. J. Math. 1904. Vol. 26. P. 1-30. 10Weiss M. J. On simply transitive groups // Bull. Amer. Math. Soc. 1934. Vol. 40. P. 401-405. 11Wielandt H. Finite permutation groups // New York: Acad. Press, 1964.
12The GAP Group. GAP — Groups, Algorithms, and Programming, Version 4.4, Aachen, St Andrews, 2004 ().
Апробация работы. Основные результаты диссертации докладывались на международной конференции „Алгебра и ее приложения", посвященной 75-летию В.П. Шункова (Красноярск, 2007 г.), на 38-й Молодежной школе-конференции „Проблемы теоретической и прикладной математики" (Екатеринбург, 2007 г.), на Международной школе-конференции по теории групп (Челябинск, 2008 г.) и на алгебраическом семинаре ИММ УрО РАН. Исследования, проведенные в диссертации, были поддержаны грантом РФФИ N 06-01-00378.
Публикации. Основные результаты диссертации опубликованы в [1]-
и.
Структура и объем работы. Диссертация состоит из введения, содержащего формулировки основных результатов, трех глав и списка литературы из 28 наименований. Общий объем диссертации составляет 70 страниц.
