Группы автоморфизмов ассоциативных схем тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Санкт-Петербургский государственный университет

На правах рукописи

ПОНОМАРЕНКО ИЛЬЯ НИКОЛАЕВИЧ Группы автоморфизмов ассоциативных схем

01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Санкт-Петербург - 2006

Работа выполнена в Санкт-Петербургском отделении математического института им. В.А. Стеклова Российской Академии Наук

Официальные оппоненты:

доктор физико-математических наук, профессор Николай Александрович Вавилов

доктор физико-математических наук, член-корреспондент РАН, профессор Александр Алексеевич Махнев

доктор физико-математических наук, Максим Михайлович Скриганов

Ведущая организация:

Математический институт имени В.А.Стеклова РАН

Защита состоится 2006 г. в I ■ в О часов на

заседании диссертационного совета Д 212.232.29 по защите диссертаций на соискание учёной степени доктора наук при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28, математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Защита будет проходить в Петербургском отделении Математического института имени В.А.Стеклова РАН по адресу: Санкт-Петербург, наб. реки Фонтанки, д. 27.

Автореферат разослан ^ ^ <\л«-,уД-АА 2006 г.

Учёный секретарь совета

доктор физико-математических наук

профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В своей известной монографии "Геометрическая алгебра" М.Артин па стр.79 пишет: "В современной математике исследование симметрии данной математической структуры приводит, как правило, к наиболее значительным результатам". Поскольку значительная часть математических структур может быть определена в терминах отношений (различной арности), естественно изучать группы автоморфизмов семейств отношений. Такой подход впервые возникает у Галуа, который фактически определяет группу уравнения, как группу автоморфизмов семейства отношений на множестве его корней. По сути тот же подход используется и в работе Шура (1933), в которой он обобщает теорему Всрнсайда о примитивных группах перестановок с регулярной циклической подгруппой посредством изучения бинарных отношений, инвариантных относительно последней. Алгебраическим аналогом возникающих при этом комбинаторных структур являются кольца, известные теперь как кольца Шура. Систематическое использование этого подхода было начато Виландтом (1969) и привело к появлению метода инвариантных отношений, суть которого состоит в изучении произвольных групп, как групп автоморфизмов подходящих семейств отношений. Уже в случае бинарных отношений этот метод позволил получить характеризацию некоторых классов групп рант 3 и построить ряд спорадических простых групп таких, например, как группа Хигмана-Симса.

Общая теория семейств бинарных отношений, наследующих свойства бинарных инвариантных отношений групп перестановок, была заложена Д.Хигманом (1970) и, независимо, в работе Вейсфейлераи Лемана (1968). Такие семейства были названы когерентными конфигурациями, более современное название которых - ассоциативные схемы или просто схемы -связано с появлением двух известных монографий: Баннаи и Ито (1984), где теория схем отношений рассматривалась как обобщение теории представлений конечных групп, и Врауэра, Коэна и Ноймайера (1989), где класс схем дистанционно-регулярных графов изучался с алгебраической, геометрической и комбинаторной точек зрения. Среди наиболее впечатляющих применений теории схем отметим отметим классическую теорему Бабаи (1981), дающую асимптотически точную оценку максимального порядка примитивной группы перестановок, не являющейся дважды транзитивной.

Одной из наиболее важных задач математики является нахождение полного множества инвариантов изоморфизма объектов заданной категории. В случае конечных объектов такое множество всегда может быть выбрано конечным и потому естественная проблема состоит в поиске иаи-

меньшего количества инвариантов. С алгоритмической точки зрения проблема изоморфизма заключается в оценке сложности наиболее эффективного алгоритма, проверяющего изоморфизм двух заданных объектов. Известно, что проблема изоморфизма конечных алгебраических структур сводится к проблеме изоморфизма конечных графов, являющейся одной из наиболее известных нерешённых проблем теории сложности вычислений. Именно эта проблема привела Вейсфейлера и Лемана в 1968 г. к открытию клеточных алгебр, которые есть ни что иное как алгебры смежности схем отношений. Связав с каждым графом клеточную алгебру, порождённую его матрицей смежности, они фактически показали, что проблема изоморфизма графов полиномиально эквивалентна проблеме нахождения группы автоморфизмов схемы отношений. Эти идеи, актуальные и в настоящее время, привели к появлению ряда эффективных алгоритмов решения последней проблемы в естественных классах графов и схем, определяемых с помопц>ю тех или иных алгебраических ограничений.

Исходным пунктом настоящей работы является соответствие Галуа между множеством всех схем С на конечном множестве V и множеством всех подгрупп Г симметрической группы Зут(У), задаваемое отображениями

Ск+Аи^С), ГН-1пу(Г), (1)

где Аи1(С) - группа автоморфизмов схемы С и 1пу(Г) - схема орбит группы Г относительно её индуцированного действия на V2. Замкнутыми объектами в этом соответствии являются шуровы схемы и 2-замкнутые группы. Следует отмстить, что соответствие (1), не являясь взаимнооднозначным, становится таковым при некоторых условиях. Важный пример такой ситуации возникает для классов схем и групп, для которых справедлив аналог теоремы Биркгофа о дважды стохастических матрицах; соответствующая теория развивается в главе 6. Правая часть соответствия (1) легла в основу метода Шура, применяемого к схемам, группа автоморфизмов которых содержит регулярную подгруппу. Накладывая на такие схемы условие инвариантности относительно автоморфизмов этой подгруппы, удаётся существенно обобщить известную теорему Бернсайда-Шура о группах перестановок (глава 4).

С вычислительной точки зрения можно легко найти схему группы перестановок эффективным алгоритмом, в то время как нахождение группы автоморфизмов - трудная задача, полиномиально эквивалентная проблеме изоморфизма графов. Эта задача упрощается, если известна некоторая априорная информация о группе автоморфизмов или сё можно получить изучая структуру соответствующей схемы. В первом случае примером является долгое время остававшаяся нерешённой проблема на-

хождения эффективного алгоритма построения группы автоморфизмов циркулянтной схемы (у такой схемы группа автоморфизмов содержит регулярную циклическую подгруппу). Эта проблема полностью решается в главе 5 на основе значительного развития теории таких схем, построенной в последнее время. Во втором случае, используя известную теорему Жордана о линейных группах, мы доказываем, что группа автоморфизмов произвольной однородной схемы содержит разрешимую подгруппу, индекс которой ограничен некоторой функцией, зависящей от инвариантов линейных представлений алгебры смежности этой схемы. Это позволяет построить алгоритм для нахождения канонической формы и группы автоморфизмов в классе всех схем, работающий полиномиальное время, когда упомянутые инварианты растут медленно в сравнении со степенью схемы (глава 3).

Цель работы. Основной целью диссертации является исследование на основе соответствия (1) групп автоморфизмов ассоциативных схем как с сугубо теоретической, так и с алгоритмической точек зрения.

Методы исследований. Применяются общие методы теории групп перестановок, теории представлений групп и алгебр, теории сложности вычислений, а также новые методы, предложенные автором, включая обобщение метода инвариантных отношений, введённого Виландтом.

Научная новизна. В диссертации получены следующие новые результаты.

1. Получено обобщение теоремы Бернсайда-Шура о группах перестановок с регулярной подгруппой, основанное на построении теории колец Шура над конечными коммутативными кольцами.

2. Доказан аналог теоремы Жордана о группах с точным линейным представлением для транзитивных групп перестановок с ограниченными степенями неприводимых представлений, входящих в перестановочное.

3. Введено и изучено понятие комбинаторной компактности ассоциативных схем и групп перестановок, позволяющее значительно обобщить теорему Биркгофа о дважды стохастических матрицах.

4. Изучены группы автоморфизмов схем Кэли над циклической группой. В частности, получена характеризация разрешимых групп в этом классе.

5. Введены и полностью охарактеризованы лесовидные схемы и их группы автоморфизмов. Полученные результаты позволили объяснить с алгебраической точки зрения эффективность комбинаторных алгоритмов проверки изоморфизма для нескольких хорошо известных классов графов.

6. Впервые построен алгоритм полиномиальной сложности для рас-

познавания схем Кэли над циклической группой и вычисления их групп автоморфизмов. Доказало, что с его помощью можно эффективно найти полную систему попарно неэквивалентных представлений Кэли таких схем.

7. Определена каноническая форма в классе всех ассоциативных схем, сложность вычисления которой растёт полиномиально при медленно растущей максимальной кратности неприводимых представлений их алгебр смежности

8. Описан эффективный алгоритм вычисления 2-замыкашш групп перестановок в классе разрешимых групп, включающем все нильпотентные группы и все группы нечётного порядка.

9. Введена конструкция сплетения схемы с группой перестановок, позволяющая строить новые бесконечные семейства примитивных нешуро-вых схем. Получены необходимые и достаточные условия примитивности и шуровости схемы, получающейся с помощью такого сплетения.

Апробация работы. Основные результаты диссертации многократно докладывались и обсуждались на алгебраическом семинаре им. Д.К.Фад-десва (СГ16ГУ), на семинаре по теории сложности вычислений (ПОМИ), на семинаре но теории представлений и динамическим системам (ПОМИ), на семинаре по информатике и компьютерным технологиям (СПИИРАН), на университетских математических семинарах г. Ренна (Франция) и it. Бонна и Мюнхена (Германия), а также были представлены на следующих конференциях:

1. Вторая международная конференция "Методы логики в математике", Санкт-Петербург, Россия, июль 2005 г. (приглашённый доклад),

2. Международная конференция "Открытые проблемы теории ассоциативных схем", Пусан, Корея, июль 2004 г. (приглашённый доклад),

3. Вторая международная конференция по математическим алгоритмам, Нижний Новгород, Россия, июнь 1995 г. (приглашённый доклад),

4. Международная конференция "Последние достижения в теории ассоциативных схем", Санкт-Петербург, Россия, июль 2005 г.,

5. Международная конференция "Ассоциативные схемы, коды и дизайны", Пусан, Корея, июль 2004 г.,

6. Шестая международная конференция по приложениям компьютерной алгебры (IMACS), Санкт-Петербург, Россия, июнь 2000 г.,

7. Пятый чешско-словацкий симпозиум но комбинаторике, теории графов, алгоритмам и их приложениям, Прага, Чехия, июль 1998 г.,

8. Международная конференция "Формальные степенные ряды и алгебраическая комбинаторика", Торонто, Канада, июнь 1998 г.,

9. Международная алгебраическая конференция памяти Д.К.Фадде-ева, Санкт-Петербург, Россия, июнь 1997 г.,

10. Международная конференция памяти Л.А.Калужнина "Алгебра и комбинаторика: взаимные связи и приложения", Кёнигштейн, Германия, апрель 1994 г.,

11. Международная конференция по алгебраической комбинаторике (ALCOM), Владимир, Россия, август 1991 г.,

12. Восьмая всесоюзная конференция по математической логике, Москва, сентябрь 1986 г.

Практическая ценность. Работа носит теоретический характер. Её результаты могут быть использованы в алгебраической комбинаторике, теории групп, вычислительной алгебре и теории графов, а также в теории планирования эксперимента и в математических моделях телекоммуникационных сетей связи.

Публикации. Основное содержание диссертации опубликовано в 13 научных статьях, список которых приведён в конце автореферата.

Структура и объём работы. Диссертация состоит из введения, шести глав и списка литературы, содержащего 81 название. Общий объём диссертации составляет 118 страниц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении даётся общий обзор результатов, относящихся к тематике диссертации, и обсуждаются мотивировки решаемых в ней задач.

Ниже для конечного множества V через \У\ обозначается его мощность, а через Бут (У) - группа всех перестановок элементов этого множества.

Глава 1. Схемы отношений, группы перестановок, алгоритмы

Эта глава носит вводный характер; здесь приводятся необходимые определения и обозначения, используемые на протяжении всей работы.

Пусть V - конечное множество. Следуя Д.Хигману, под когерентной конфигурацией, схемой отношений или просто схемой на V мы понимаем пару С = [V, 71), где 72. - замкнутое относительно перестановки координат разбиение множества V2 такое, что диагональ множества V2 является объединением элементов из 72. и для каждой тройки элементов Д, 6', Т е 72. определено неотрицательное целое число Сд удовлетворяющее равенству

= («,м)€5}|, (и,и>) 6 Т. (2)

Последнее свойство является комбинаторным выражением того факта, что матрицы смежности Л (Я) базисных отношений Л € К схемы С образуют линейный базис, порождённой ими матричной алгебры, называемой алгеброй смежности этой схемы. На языке алгебр смежности легко ввести стандартные понятия для схем, включающие факторы, ограничения и расширения, а также определить частичное упорядочение в классе 21у всех схем на множестве V, использованное в соответствии (1).

Схемы С и С' называются изоморфными, если существует биекция множества V точек схемы С яа множество точек схемы С', сохраняющая базисные отношения. Группа всех изоморфизмов, т.е. определённых выше биекций, схемы С на себя обладает нормальной подгруппой

АШ(С) = {/ е Яут(У) : Я1 = Я V Я 6 Я},

называемой группой автоморфизмов схемы С\ элементы этой группы называются автоморфизмами схемы. Обратно, для любой группы перестановок Г < 5уш(1/) определяется схема

Ьу(Г) = (V, ОгЬа(Г)),

где ОгЬ'2 (Г) - множество 2-орбит группы Г, т.е. орбит её индуцированного действия на множестве V2. При этом схема оказывается однородной (соотв. примитивной) в том и только в том случае, когда группа Г тран-зитивна (соотв. примитивна).

В заключительной части главы 1 мы описываем известную алгоритмическую технику, используемую для работы со схемами и группами перестановок. Здесь и далее говоря об эффективных алгоритмах мы имеем в виду те из них, время работы которых полиномиально зависит от размера входа. В случае схем основные алгоритмы (такие как нахождение факторов и ограничений) являются вариантами известных алгоритмов на графах1, что неудивительно, поскольку схемы могут рассматриваться как специальные случаи раскрашенных полных графов. Менее известен алгоритм Вейсфейлера-Лемана, строящий множество базисных отношений расширения произвольной схемы (теорема 1.6). Стандартные эффективные алгоритмы для вычислений с группами перестановок также хорошо известны и описаны в монографии Сереша (2003). Наш основной инструмент здесь - алгоритм Бабаи-Лакса, вычисляющий для схемы С 6 и разрешимой группы Г < Эут^) группу КиЬ(С) Л Г (теорема 1.7).

Глава 2. 2-замыкания групп перестановок

1Под графом можно понимать обычный граф, ориентированный граф или даже рёберно раскрашенный граф.

Соответствие (1) между схемами и группами перестановок показывает, что изучение групп автоморфизмов схем есть изучение 2-замкнутых групп. Исследование последних начинается с хорошо известных операций прямой суммы и тензорного произведения, представляющих два естественных действия прямого произведения СI х С2 групп перестановок Ст < Бут (У!) и С?2 < Вуш(1А) на дизъюнктном объединении VI и \г2 и на декартовом произведении VI х У2. Каждой из этих операций отвечает соответствующая операция для схем и мы приводим формулы для группы автоморфизмов результирующей схемы. В случае тензорного произведения мы также доказываем минимальность соответствующей схемы (теорема 2.3). Все эти результаты затем используются во всех последующих главах.

Изучение сплетений схем и их связей со сплетениями групп перестановок начинается с хорошо известного случая импримитивного сплетения. Каждая однородная схема, изоморфная такому сплетению, удовлетворяет специальному условию (определение 2.5), которое в гораздо менее общей ситуации уже возникало при изучении колец Шура над циклической группой. Мы описываем группу автоморфизмов произвольной схемы, удовлетворяющей этому условию (теорема 2.6), получая в качестве следствия известную формулу для группы автоморфизмов однородного сплетения.

До настоящего времени в теории схем не было известно аналога примитивного действия сплетения для групп перестановок, играющего важную роль в изучении примитивных групп. До некоторой степени именно этим обстоятельством можно объяснить отсутствие регулярных конструкций бесконечных семейств примитивных нешуровых схем. Мы определяем и изучаем экспоненцирование С Т К схемы С с группой перестановок К, которое в случае, когда С — 1пу(С) для некоторой группы перестановок С?, совпадает со схемой группы перестановок С Т Л', индуцированной примитивным действием сплетения <3 ! К (см. § 2.3). Вопрос о шуровости экспоненцирования полностью решается следующей теоремой.

Теорема 2.8. Схема С 1 К является шуровой тогда и только тогда, когда схема С шурова.

Хорошо известно, что группа С 1 К примитивна в том и только в том случае, когда группа <3 примитивна п нерегулярна, а группа К транзи-тнвна. Обобщением этого результата служит следующая теорема, которая вместе с теоремой 2.8 и позволяет построить бесконечное семейство примитивных нешуровых схем, исходя из одной такой заданной схемы.

Теорема 2.10. Пусть С е 21^ и К < Зут(-АГ). Тогда схема С \ К примитивна тогда и только тогда, когда группа К т-ранзитивна и схема С прилштивна и 'нерегулярна.

В § 2.4 мы изучаем проблему нахождения 2-замыкания группы перестановок с алгоритмической точки зрения. Эта проблема является частным случаем проблемы нахождения группы автоморфизмов схемы, но в этом конкретном случае в качестве начальной информации на входе алгоритма задана нетривиальная подгруппа группы автоморфизмов этой схемы. Для абелевых групп проблема легко решается с помощью алгоритма Бабаи-Лакса, поскольку абелевость сохраняется при взятии 2-замыкания. Значительно более широкий класс групп, содержащий с каждой группой и её 2-замыкание, может быть описан следующим образом.

Под секцией транзитивной группы перестановок С? будем понимать любую группу перестановок вида Сх/в, где X - блок группы С, являющийся объединением некоторых классов С-инвариантного отношения эквивалентности Е. Секциями интранзитивной группы по определению считаем секции ей транзитивных составляющих. Обозначим через О класс всех конечных групп перестановок, у которых каждая примитивная секция чётного порядка имеет степень 2. Используя теорему Фейта-Томпсона нетрудно проверить, что этот класс состоит из разрешимых групп и включает все нильпотентные группы и все группы нечётного порядка. Более того, 2-замыкание каждой группы из <7 также принадлежит 0 (лемма 2.15).

Теорема 2.16. 2-замыкапие группы, перестановок из класса 5 может быть вычислено за полиномиальное время от степени группы.

В доказательстве этой теоремы используются описанные в предыдущих параграфах эффективные вложения интранзитивных и импрпмитив-ных групп перестановок в прямые суммы и импримитивные сплетения. В случае примитивной группы из разрешимости следует, что её стабилизатор точки может быть отождествлён с линейной группой над конечным простым полем. Последняя группа либо импрнмитивна (как линейная группа), либо примитивна. В первом случае мы используем конструкцию Супруненко для сплетения линейной группы с группой перестановок, которая позволяет эффективно вложить исходную группу в экспоненциро-вание двух меньших и применить результаты из § 2.3. В втором случае работает теория максимальных примитивных разрешимых линейных групп над конечным полем (также развитая в основном Супруненко). Используя эту теорию, удаётся доказать, что если исходная группа не является 2-замкнутой и не вкладывается в экспоненцирование, то она изоморфна (как группа перестановок) подгруппе одномерной полулинейной аффинной группы над конечным полем (следствие 2.13), и соответствующее вложение может быть эффективно найдено (теорема 2.14).

Глава 3. Каноническая форма в классе всех схем

Проблема изоморфизма графов заключается в проверке того, являются ли два заданных конечных графа изоморфными, т.е. существует ли биекция между их множествами вершин, сохраняющая отношение смежности. Известно, что эта проблема принадлежит классу NP, однако до настоящего времени неизвестны эффективные алгоритмы её решения. Наиболее быстрый из известных алгоритмов проверяет изоморфизм двух п-вершннных графов за время ПрИЧём доказательство по-

следней оценки опирается на классификацию конечных простых групп.

Неудачи в попытках найти эффективный алгоритм проверки изоморфизма в классе всех графов привели к исследованиям проблемы изоморфизма для специальных классов графов. Были найдены эффективные алгоритмы в классе всех графов ограниченной степени (Лаке, 1982) и в классе всех графов с ограниченной кратностью спектра матрицы смежности (Бабаи-Григорьев-Маунт, 1982). В обеих работах время работы алгоритма для графов с п вершинами оценивается сверху величиной п°(т), где число т не зависит от п, но зависит от максимальной степени графа в первом случае и совпадает с максимальной кратностью спектра во втором. Возникает естественный вопрос: можно ли улучшить сложность алгоритма, убрав число т из показателя оценки сложности? В главе 3 мы отвечаем положительно на этот вопрос построением алгоритма проверки изоморфизма в классе всех графов, сложность которого полиномиальна не только при постоянном то, но и для всех то, не превосходящих /(п), где / - некоторая функция, медленно растущая с ростом п.

Используя вариант алгоритма Вейсфейлера-Лемана, строящий каноническое упорядочение множества базисных отношений результирующей схемы, легко свести проблему изоморфизма графов к проблеме изоморфизма упорядоченных схем, т.е. схем с упорядоченным множеством базисных отношений. Далее, отображение СР из множества всех упорядоченных схем на V в множество всех упорядоченных схем на {1,...,п}, где п — |У|, называется канонической формой, если

С¥(С) = С и С^С' » СР(С) = С¥{С')

для всех упорядоченных схем С, С 6 21V- Любая биекция /г, для которой С'1 = СР(С), называется канонической пометкой схемы С. Множество всех таких биекций образует класс смежности СЬ(С) = Аи<;(С)/1, называемый классом смежности канонических пометок этой схемы относительно канонической формы СР. Таким образом, проблема изоморфизма графов сводится к проблеме нахождения канонической формы в классе упорядоченных схем или, эквивалентно, к нахождению класса смежности канонических пометок относительно некоторой канонической формы. Заметим, что решая последнюю задачу мы одновременно находим и группу автоморфизмов схемы.

Реализация описанного подхода основана на хорошо известной теореме Жордана, утверждающей, что каждая конечная группа G < GLd(C) содержит нормальную абелеву подгруппу А, для которой

[G-. А] < J(d),

где .7 - некоторая функция, называемая ниже функцией Жордана. Известно также, что J(d) < d°(d !log dK Используя теорему Жордана, Ай-закс и Пассман (1964) доказали, что если степени всех представлений группы G, неприводимых над С, не превосходят d, то [G : А] < J (2d) для некоторой абелевой подгруппы А группы G. Следующая теорема показывает, что для транзитивной группы перестановок G нет необходимости рассматривать все неприводимые представления, если абелевость А заменить разрешимостью. Ниже через d(G) обозначается максимальная степень неприводимого представления группы G, входящего в её перестановочное представление.

Теорема 3.5. Пусть G - транзитивная группа перестановок. Тогда найдётся нормальная разрешимая подгруппа А группы G, для которой [G: А] < J(dy°62 d, где d = d{G) и J - функция Жордана.

Обозначим через Qm множество всех транзитивных групп G, для которых d(G) < т. Тогда теорема 3.5 утверждает, что для каждого натурального т число

F(m) = sup [G : Sol(G)], сед,,,

где Sol(G) - максимальная разрешимая нормальная подгруппа группы G, не превосходит J(m)1°s'-i m. Связь между теоремой 3.51 и упомянутым выше результатом Айзакса и Пассмана легко усматривается, поскольку каждое неприводимое представление группы G входит в регулярное представление этой группы, являющееся перестановочным для действия G на себе правыми сдвигами, которое, очевидно, является транзитивным.

Ещё одним ингредиентом нашего подхода является алгоритмическое обобщение верхней оценки для порядка примитивной группы перестановок, ранее полученной автором. Именно, по аналогии с понятием базы и несводимой базы групп перестановок мы вводим соответствующие понятия для схем (п. 3.3.2) и доказываем следующую теорему, которая даёт, в частности, верхнюю оценку на порядок группы автоморфизмов примитивной схемы С в терминах максимального размера 6(C) её несводимой базы и минимальной степени d(C) её нерефлексивного базисного отношения.

Теорема 3.13. В классе всех примитивных схем все элементы класса смежности канонических пометок CL(С) (а, следовательно, и группы

автоморфизмов Aut(C),) схемы С степени п можно перечислить за время где d = d(C) ub = b(C). Более того, | CL(C)| < db~xn.

Отметим, что для примитивной схемы С оба числа d(C) и Ъ{С) можно оценить сверху, используя инварианты естественного линейного представления её алгебры смежности W (см. § 3.1). Именно, пользуясь полупростотой этой алгебры над С, разложим её стандартное представление в прямую сумму неприводимых представлений. Тогда её главное неприводимое представление, переводящее матрицу смежности базисного отношения R схемы С в число d(R), имеет степень и кратность, равные 1. Все же остальные неприводимые представления алгебры W могут иметь большие кратности. Максимальная из них, обозначаемая через т(С), не возрастает при расширениях, факторизациях и ограничениях (Следствие 3.2), и, более того, для любой примитивной схемы С имеет место неравенство

Ь(С) < т(С), d{C) < т(С),

доказанное автором и Евдокимовым (1999).

Сведение проблемы построения канонической формы упорядоченной схемы к случаю примитивной схемы проводится в § 3.4. С технической точки зрения удобнее ввести понятие канонической формы схемы на V, ограничивая множество всех возможных изоморфизмов на некоторую группу G < Sym(V) или даже на класс смежности по этой группе. В этой относительной ситуации, используя хорошо известную технику вычислительной теории групп, можно построить каноническую форму схемы за время t2n°(l\ где t - максимальное из чисел [Н : Sol(-if)], когда II пробегает множество всех транзитивных составляющих группы G (лемма 3.14). Такой приём позволяет свести общий случай к случаю однородной схемы. Используя теорему 3.13, если такая схема примитивна, и рекурсию в противном случае, мы доказываем следующий результат.

Теорема 3.15. Каноническая пометка и группа автоморфизмов схемы С степени п могут быть найдены за время f{m)п°<-1\ гдет = т{С) и f(m) = т"1"1 F(m)2.

Пусть Г - граф с произвольной раскраской рёбер в s > 1 цветов. Обозначим через Ai = А;(Г) матрицу смежности бинарного отношения Ri, состоящего из всех рёбер цвета i = 1,..., s. Положим

т(Г) = min m(Ai), i

где m(Ai) - максимальная кратность жорданова блока матрицы АТогда, используя стандартные методы линейной алгебры, можно найти число 'пг(Г) за полиномиальное время от числа вершин графа Г. Поэтому за

то же время проверяется и принадлежность графа к классу всех рёбер-но раскрашенных графов Г, для которых т(Г) < т. С другой стороны, легко видеть, что для произвольного раскрашенного по рёбрам графа Г имеет место неравенство т(С) < т(Г), где С - минимальная схема на множестве вершин этого графа, содержащая каждое из отношений г = 1,..., е. Поэтому в качестве простого следствия теоремы 3.15 мы получаем следующее утверждение.

Теорема 3.16. В классе всех рёберно раскрашенных п-вершинных графов Г, для которых 7тг(Г) < т, изоморфизм может быть проверен за время /(т)п°(1), где /(т) = тт~1Г(т)2.

Неравенство из теоремы 3.5 было улучшено Айзаксом (2000), доказавшим, что F(m) < J(m). Кроме того, используя классификацию конечных простых групп, (СРЯС) Пибер (1997) доказал, что J(m) < (т!)0<1К Таким образом,

/(т) < еО('"2/Ьят) и /(т) < еО(т1овт)

Это показывает, что время работы алгоритма проверки изоморфизма графов из теоремы 3.16 зависит от п полиномиально безусловно, когда т < О^к^тгк^к^п)1/2), и при условии СЕБС, когда т < О(\о&п/ k>g п).

Глава 4. Теорема Бернсайда-Шура и её обобщение

В этой и следующей главах исследуются схемы, группа автоморфизмов которых содержит регулярную подгруппу. Фактически именно алгебры смежности таких схем в контексте теории групп перестановок изучал Шур, а затем Виландт. Отправной точкой результатов этой главы служит следующее известное утверждение о группах перестановок, которое мы обобщим на схемы, допускающие регулярную абелеву группу автоморфизмов.

Теорема (Бернсайд-Шур). Каждая примитивная конечная группа перестановок, содержащая регулярную циклическую подгруппу, дважды транзнтивна или изоморфна как группа перестановок подгруппе аффинной группы Авр! (р), где р - простое число.

В действительности Бернсайд (1911) доказал эту теорему для групп перестановок, степень которых равна степени некоторого простого числа, и предположил, что её утверждение выполняется также в случае произвольной абелевой регулярной подгруппы, не обязательно циклической. Шур (1933) опроверг эту гипотезу и доказал, что каждая примитивная группа перестановок составной степени, содержащая регулярную циклическую подгруппу, дважды транзитивна. Этот результат позднее был

обобщён Виландтом (1964) (см. следствие 4.9).

В отличие от метода Бернсайда, использовавшего теорию характеров, идея Шура состояла в следующем. Пусть Г - группа перестановок, содержащая регулярную подгруппу G. Тогда подмодуль .Д(Г) группового кольца С [С] группы G, натянутый на орбиты стабилизатора точки группы Г, образует подкольцо последнего кольца (выбирая точку, мы отождествляем эти орбиты с подмножествами группы G). Кольцо Л (Г) является частным случаем кольца Шура (или S-кольца) над группой G. Шур заметил, что группа Г дважды транзитивна (соотв. примитивна) тогда и только тогда, когда S-кольцо Л{Т) имеет ранг 2 (соотв. примитивно). Таким образом, теорема Бернсайда-Шура в случае, когда степень группы Г является составным числом, непосредственно вытекает из следующей теоремы, доказанной Шуром: каждое примитивное S-кольцо над циклической группой составного порядка имеет ранг 2.

Метод Шура был развит Виландтом в известной монографии о группах перестановок, в одной из глав которой строится теория S-колец над произвольной группой G. В общем случае такое кольцо представляет собой произвольное подкольцо группового кольца C[G], содержащее единицу и замкнутое относительно естественной инволюции и покомпонентного умножения. Внландт заметил, что, во-первых, ire каждое S-кольцо является шуровым, т.е. кольцом вида Л(Г) для подходящей группы перестановок Г, и, во-вторых, фактически указал естественное линейное представление

. рс ■■ C[GJ — MatG(С), д <—> Рд,

кольца C[G], сопоставляющее элементу д перестановочную матрицу Рд, отвечающую левому умножению на. д. Это представление индуцирует изоморфизм категории S-колец на категорию алгебр смежности ассоциативных схем, допускающих группу Griaht в качестве группы автоморфизмов. Последние схемы называются схемами Кэли над группой G; каждое базисное отношение такой схемы может рассматриваться как множество рёбер некоторого графа Кэли над G. Указанное соответствие между кольцами Шура и схемами Кэли позволяет в каждом случае использовать наиболее удобный язык, так кольцевой вариант теоремы Бернсайда-Шура, рассматриваемый в главе 4, постоянно используется в главе 5 применительно к схемам Кэли.

Основным инструментом, который используется при доказательстве теоремы Бернсайда-Шура является теорема Шура о мультипликаторах, утверждающая, что для любого S-кольца А над абелевой группой G имеет место включение:

Z(Am(G)) < Iso(^), (3)

где .Z(Aut(G)) - центр группы Aut(G), a Iso(«4) - множество шоморфиз-

мов Э-кольца А на себя. Существуют примеры Я-колец, показывающие, что в общем случае группу 2(Аи1(С?)) нельзя заменить на большую подгруппу в Аи1;(С). С другой стороны, группа Z(A\li{G)) достаточно мала и, во многом, именно этим обстоятельством объясняется тот факт, что наиболее сильные результаты в теории Б-колец получены именно в случае циклической группы С, когда .Е(Аи1;(С)) — Аи^С). В этом смысле представляется естественным заменить группу в левой части включения (3) на произвольную группу К < Аи(,(С) и изучить возникающие при этом Л'-инварнантпыс Э-кольца над С.

Необходимая для дальнейшего теория /^-инвариантных Э-колец над абелевыми группами воссоздаётся в п. 4.4.1. Здесь доказывается, в частности, что двойственное Э-кольцо А"-инвариантного Я-кольца Л является /^-примитивным в том и только в том случае, когда таковым является А (теорема 4.17). Введённое здесь понятие К-примитивности Б-кольца А над С? совпадает с обычным, когда группа К тривиальна, и означает, что каждая ЛГ-ннвариантная .Д-подгруппа группы С? является тривиальной (под Л-подгруппой понимается любая подгруппа группы б, сумма элементов которой принадлежит Л). Полное описание всех /{"-примитивных Э-колец над абелевой р-группой Р, используемое в доказательстве основного результата этой главы (теорема 4.10 ниже), получается при условии, что группа К < Аш(Я) абелева и

Р \ {в>: : к <Е А'} — /{'-инвариантная подгруппа группы Р (4)

для некоторого элемента е € Р (теорема 4.8), где ек - образ этого элемента под действием автоморфизма к. Ключевой момент здесь - теорема о разделяющей подгруппе (теорема 4.13), описывающая некоторые специальные подгруппы группы С, не являющиеся Л-подгруппами. Отметим в этой связи, что все известные доказательства теоремы Виландта (следствие 4.9 ниже), восходят к его исходному доказательству. Однако детальный анализ показывает, что большая его часть является частным случаем нашей теоремы о разделяющей подгруппе.

Важным примером /^-инвариантного Б-кольца над абелевой группой ¿7 является центральное в этой главе понятие Б-кольца над конечным коммутативным кольцом.

Определение 4.5. Пусть А - Б-колъцо над группой С и К - конечное коммутативное кольцо. Тогда А называется 5-колъцом над кольцом В., если в совпадает с аддитивной группой этого кольца и А инвариантно относительно действия подгруппы Кц группы Аи1;(С?), индуцированного действием мультипликативной группы Нх на умножениями.

Формула (3) показывает, что каждое Э-кольцо над циклической груп-

пой порядка п есть по сути ни что иное как Б-кольцо над кольцом Ъп. Ещё одним примером Б-кольца над Я оказывается любое Б-кольцо А вида Л (Г), где Г - произвольная группа перестановок на П, для которой справедливы включения:

Т(Л) < Г < АСЬ^Я),

где Я - конечное коммутативное кольцо и Т(Я) - подгруппа группы Бут(Я), состоящая из всех аддитивных сдвигов на элементы из Я. Мы называем его циклотомическил1 Б-кольцом над Я. В случае, когда Я -конечное поле, схемы циклотомических колец есть в точности циклото-мические схемы, введённые Ф. Дельсартом.

Б-кольцо над конечным коммутативным кольцом Я называется квазипримитивным, если оно Л'я-прнмнтивно. Если Я не изоморфно произведению двух колец, одним из которых является 22 х то оно порождается своими единицами, и поэтому в этом случае квазипрпмитивность Б-кольца Л над Я означает в точности, что {0} и Я являются единственными идеалами кольца Я, которые одновременно являются и Д-подгруппами группы Я+. Следующее утверждение может рассматриваться как обобщение теоремы Бернсайда-Шура.

Теорема 4.10. Пусть Я - конечное коммутативное кольцо с единицей. Если по крайней мере, одна его прилшрная компонента локальна, то каждое квазипримитивпое 5-колйцо над Я имеет 'ранг 2 или является и,иклотомическим. В последнем, случае Я является полем.

Чтобы понять, почему теорема 4.10 действительно обобщает теорему Бернсайда-Щура, рассмотрим примитивную группу перестановок Г, содержащую регулярную циклическую подгруппу С?. Тогда по теореме Шура о мультипликаторах не умаляя общности можно считать, что -Л(Г) является Б-кольцом над кольцом ЪГ11 где п = |С?|. Из примитивности группы Г следует, что Л (Г) - примитивное Б-кольцо над группой и потому квазппримитивное Б-кольцо над кольцом Ъп. Кроме того, каждая при-марная компонента кольца Zn является, очевидно, локальным кольцом. Таким образом, для Б-кольца .А(Г) выполнено утверждение теоремы 4.10 (при Я = 2П). Если *4(Г) - Б-кольцо ранга 2, то группа Г дважды тран-знтивна. В противном случае, -4(Г) - цнклотомическое Б-кольцо, п = р -простое число и потому Г < ЛСЬх (р).

Как уже упоминалось выше, в процессе доказательства мы используем описание всех /{"-примитивных Б-колец над абелевой р-группой Р в случае, когда группа К < Аи1;(Р) абелева и для некоторого элемента е 6 Р выполнено условие (4). Мы называем (К, е) локальной парой на Р. Естественными примерами локальных пар являются пары вида {Ки, 1л),

где Я - конечное локальное коммутативное кольцо и Р — Я+. Следующая теорема показывает, что других примеров нет.

Теорема 4.11. Пусть Р - конечная абелева р-группа. Тогда отображение

Я >-* {КЦ, 1д)

устанавливает взаимно однозначное соответствие между множеством всех локальных коммутативных колец на Р и множеством всех локальных пар на Р. Более того, два таких кольца изоморфны тогда и только тогда, когда соответствующие подгруппы сопряжены в группе А мЬ{Р).

Глава 5. Канонические формы циркулянтных схем

Конечный граф называется циркулянтиым, если его группа автоморфизмов содержит полный цикл2, то есть перестановку, циклическое разложение которой состоит из единственного цикла полной длины. Эквивалентно, граф допускает регулярную циклическую группу автоморфизмов и, следовательно, изоморфен графу Кэли над циклической группой.

Одна из основных вычислительных задач, связанных с циркулянтны-ми графами, состоит в нахождении эффективного алгоритма их распознавания. (Указанная задача является частным случаем известной МР-полной задачи, в которой требуется определить, имеет ли данный граф автоморфизм без фиксированных точек.) Попытки решения этой задачи касались распознавания отдельных классов циркулянтных графов, однако общая проблема до настоящего времени оставалась открытой. В главе 5 приводится её полное решение.

Более простая задача, касающаяся циркулянтных графов, состоит в нахождении эффективного алгоритма проверки их изоморфизма. В действительности, она полиномиально сводится к задаче распознавания, поскольку два циркулянтных графа с одинаковым числом вершин изоморфны тогда п только тогда, когда их дизъюнктное объединение само является циркулянтным графом. Здесь мы приводим алгоритм нахождения канонической пометки циркулянтных графов (см. п. 3.3.1). Отметим, что проблема изоморфизма графов Кэли над циклической группой (являющаяся частным случаем проблемы изоморфизма циркулянтных графов) широко изучалась в последние сорок лет и была независимо решена Му-зычуком (2001).

Подход, используемый в данной работе, опирается на следующее понятие фактически введённое автором в 1992 г. Ниже через Сус(С) мы обозначаем множество полных циклов группы перестановок С.

2Ниже такие автоморфизмы будут называться циклическими.

Определение 5.9. Множество 5 С Сус(С) называется циклической базой группы перестановок С, если каждый элемент из Сус(С) сопряжён в С в точности с одним элементом множества Б. Циклическая база схемы (соотв. графа) определяется как циклическая база её (соотв. его) группы автоморфизмов.

Циклические базы групп были изучены Музычуком (1999), который, в частности, доказал, что мощность любой циклической базы группы (7 не превосходит степени п группы С (а по модулю классификации конечных простых групп даже ¡р(п), где ¡р - функция Эйлера). Здесь мы доказываем (теорема 5.32 ниже), что указанные выше задачи эффективно сводятся к задаче нахождения циклической базы графа. Последняя, в свою очередь, очевидным образом сводится к аналогичной задаче для схем, решение которой и занимает большую часть главы.

Для нахождения циклической базы схемы мы вводим классы квазинормальных и сингулярных схем (пп. 5.1.2 и 5.1.4) и доказываем следующую теорему.

Теорема 5.13. Каждая циркуляитная схема либо квазтюрмальна, либо сингулярна.

Оба введённых класса являются эффективно распознаваемыми (теоремы 5.7 и 5.12). Более того, группа автоморфизмов любой квазинормальной схемы содержит вычислимую за полиномиальное время разрешимую подгруппу, содержащую все циклические автоморфизмы (теоремы 5.4 и 5.7), в то время как любая сингулярная схема имеет вычислимое за полиномиальное время допустимое расширение (теоремы 5.10 и 5.12). (Расширение схемы называется допустимым, если оно собственное н каждая его циклическая база содержит циклическую базу исходной схемы). Квазинормальную схему можно представлять как схему, в.некотором смысле покрытую нормальными схемами Кэли над циклической группой (п. 5.1.1); каждая такая схема является схемой 2-орбит некоторой 2-замкнутой подгруппы голоморфа циклической группы. С другой стороны, каждая сингулярная схема обладает некоторым специальным под-фактором ранга 2 (определение 5.8); любой автоморфизм такого подфак-тора. может быть поднят до автоморфизма всей схемы (лемма 5.11). При переходе к соответствующему допустимому расширению этот подфактор регуляризуется, п рассматриваемая сингулярность тем самым разрешается.

Доказательство теоремы 5.13 базируется на изучении секций (подфак-торов) произвольной циркулянтной схемы. В случае, когда эта схема шу-рова, та же техника может быть использована для доказательства следующего утверждения, дающего явное описание примитивных секций груп-

пы автоморфизмов циркулянтной схемы.

Теорема 5.21. Пусть Г - группа автоморфизмов некоторой циркулянтной схелш. Тогда каждая примитивная секция группы Г изоморфна как группа перестановок либо симметрической группе Зут(е£) для <1 > 4, либо некоторой подгруппе аффинной группы АСЬа (р) для простого числа р.

Очевидно, что 2-замыкание любой 2-транзитивной группы совпадает с симметрической группой. С другой стороны, по теореме Бернсайда-Шура каждая примитивная группа перестановок, содержащая регулярную циклическую подгруппу, либо 2-транзитивна, либо изоморфна как группа перестановок некоторой подгруппе аффинной группы АСЬх(р) для простого числа, р. Поэтому теорема 5.21 может рассматриваться как ещё одно обобщение теоремы Бернсайда-Шура в классе всех 2-замкнутых групп.

Используя теорему 5.13 и тот факт, что разрешение сингулярностей может быть осуществлено эффективно, мы сводим упомянутую выше проблему нахождения циклической базы произвольной схемы к нахождению циклической базы квазинормальной схемы. В последнем случае удаётся построить эффективное вложение группы, порождённой всеми циклическими автоморфизмами этой схемы, в последовательное сплетение групп автоморфизмов подходящих нормальных секций (теорема 5.4 и лемма 5.5). Каждая из этих групп разрешима, и потому наша задача сводится к нахождению циклической базы разрешимой группы перестановок. В § 5.3 мы описываем алгоритм решения последней задачи для произвольной группы и доказываем, что его сложность полиномиальна в разрешимом случае (теорема 5.26). Окончательный результат даёт следующая теорема.

Теорема 5.27. Циклическая база произвольной схемы степени п может быть найдена за время

Заметим, что для вычисления группы автоморфизмов циркулянтной схемы недостаточно знать какую-либо её циклическую базу. Поэтому мы используем описание секций такой схемы, данное в теореме 5.21. Это позволяет, с одной стороны, охарактеризовать (и эффективно вычислять) разрешимые группы автоморфизмов циркулянтных схем (теорема 5.28), а с другой - контролировать поведение группы автоморфизмов при разрешении сингулярностей (лемма 5.22). Оба эти обстоятельства позволяют свести проблему вычисления группы автоморфизмов циркулянтной схемы С к случаю, когда АиЦС) < Г, где Г - разрешимая группа, заданная некоторым явно указанным множеством образующих. Последняя же проблема может быть решена эффективно с помощью алгоритма Бабаи-Лакса.

Теорема 5.29. Группа автоморфизмов циркулянтной схемы степени п может быть найдена за время

Из цитированной выше работы Музычука (2001) вытекает, что индекс группы автоморфизмов циркулянтной схемы степени п в группе изоморфизмов этой схемы не превосходит п01-гК и что представители соответствующих классов смежности могут быть эффективно вычислены. Поэтому, в качестве следствия теоремы 5.29 получаем, что и группа изоморфизмов такой схемы может быть также найдена эффективно (теорема 5.30).

Поскольку группы автоморфизмов графа и его схемы совпадают, теорема 5.27 позволяет также найти циклическую базу произвольного графа; прп этом граф является цнркулянтным тогда и только тогда, когда хотя бы одна (а потому и любая) его циклическая база непуста. Фактически это доказывает утверждение (1) теоремы 5.32 ниже. Остальные утверждения этой теоремы, кроме последнего, также следуют из теоремы 5.27.

Теорема 5.32. Пусть <?п (соответственно Сп) - класс всех графов (соответственно циркулянтных графов) на п вершинах. Тогда следующие задачи могут быть решены за время :

(1) для графа Г € 5п проверить, верно ли, что Г 6 Сп, и (если это так) найти его циклический автоморфизм,

(2) для графа Г € Сп найти его каноническую пометку,

(3) для графов Г, Г' € С71 проверить, верно ли, что Г = Г', и (если ото так) найти изоморфизм между ними,

(4) для графа Г € бп найти полную систему его попарно неэквивалентных представлений Коли,3 над циклической группой порядка п,

(5) для графа Г € найти группу Аи1(Г).

Поскольку каждый базисный граф циркулянтной схемы является цнркулянтным, в качестве следствия утверждения (2) теоремы 5.32 получаем, что каноническая форма и каноническая пометка циркулянтной схемы могут быть найдены за полиномиальное время от степени этой Схемы.

3Под представлением Кэли графа Г над группой б понимается любой изоморфный ему граф Кэли над С; два таких представления называются эквивалетстиыл+и, если найдётся изоморфизм соответствующих графов Кэли, принадлежащий АиЦО).

Глава 6. Теорема Биркгофа для схем и групп

Комбинаторная компактность. Исходным пунктом этой главы стала хорошо известная теорема Биркгофа: каждая дважды стохастическая матрица является выпуклой комбинацией перестановочных матриц. Это устанавливает следующее свойство симметрической группы: крайними точками многогранника всех дважды стохастических матриц, содержащихся в алгебре её естественного перестановочного представления, являются перестановочные матрицы элементов этой группы.

Определение 6.6. Группа перестановок <7 называется (комбинаторно) компактной, если каснсдая дважды стохастическая матрица её обёртывающей алгебры является выпуклой комбинацией перестановочных матриц Рд, д е б.

В сущности именно характеризация компактных групп и представляет собой наиболее естественный с точки зрения теории групп перестановок подход к обобщению теоремы Биркгофа. Отметим, что каждая компактная группа является 2-замкнутой и потому совпадает с группой автоморфизмов схемы её 2-орбит.

Другой, более комбинаторный, подход к обобщению теоремы Биркгофа был предложен Тинхофером (1986). Именно, для каждого графа Г обозначим через БЗ(Г) множество всех дважды стохастических матриц, коммутирующих с его матрицей смежности. Тогда теорема Биркгофа устанавливает следующее свойство полного графа Г:

ВБ(Г) = Сопу(Аи1(Г)), (5)

т.е. многогранник ВЭ(Г) совпадает с выпуклой оболочкой Сопу(Аи1;(Г)) перестановочных матриц, отвечающих автоморфизмам графа Г. Графы, для которых выполнено равенство (5), были названы графами Биркгофа и компактными графами в последующих работах, где, в частности, было показано, что изоморфизм таких графов может быть эффективно проверен с помощью простого алгоритма уточнения раскраски вершин.

Сравнение двух описанных выше подходов к обобщению теоремы Биркгофа показывает, что понятие компактного графа слишком ограничительно. Действительно, как уже было отмечено раньше, группы автоморфизмов произвольного графа Г и его схемы С совпадают. Более того,

ББ(С) С ОБ(Г),

где Ц8(С) - множество всех дважды стохастических матриц, централизующих алгебру смежности схемы С. Поэтому, придерживаясь комбинаторного подхода, естественно заменить класс компактных графов на боль-

ший класс слабо компактных графов, для которых условие (5) выполняется с заменой Г на С, т.е. схем а которых компактна. При этом оказывается, что группа автоморфизмов слабо компактного графа компактна. С другой же стороны, существуют компактные группы (и среди них некоторые регулярные), которые не являются группой автоморфизмов никакого простого графа. Таким образом, в качестве наибольшего класса компакт-пых комбинаторных объектов имеет смысл рассматривать именно класс компактных схем.

Примерами компактных схем, отличных от схем ранга 2, являются полурегулярные схемы (теорема 6.3). Каждая такая схема, будучи схемой 2-орбит полурегулярной группы, является шуровой. Более общо, имеет место следующая теорема.

Теорема 0.4. Каждая компактная схема шурова.

Таким образом, два подхода к обобщению теоремы Биркгофа, комбинаторный и теоретике групповой, оказываются по существу эквивалентными в смысле следующего результата.

Теорема 6.7. Отображения (1) индуцируют взаимно-однозначное соответствие между компактными схемами и компак?пными группами перестановок.

Далее в §6.1 мы изучаем свойства компактных схем, используя расширения, факторизации и ограничения. На языке групп перестановок первый из результатов означает, что в компактной группе стабилизатор любого множества точек компактен (теорема 6.8). Второй говорит о том, что группа., индуцированная действием компактной группы на орбитах каждой её нормальной подгруппы, компактна (теорема 6.9). Однако, транзитивная составляющая компактной группы может и не быть компактной. Это следует из того, что каждая группа перестановок является транзитивной составляющей группы автоморфизмов некоторой 1-регулярной схемы, в то время как каждая такая схема является компактной (теорема 6.10). Наконец, мы показываем что прямые суммы и простые сплетения схем компактны в том и только в том случае, когда компактен каждый из операндов (теорема 6.11). Случай тензорного произведения оказывается более сложным. Мы приводим пример двух компактных схем, тензорное произведение которых некомпактно, и показываем, что оно всегда компактно, когда одна из схем полурегулярна, а другая компактна (теорема 6.12).

Развитая техника используется в § 6.2 для характеризации компактных объектов в различных семействах схег.г, групп перестановок и графов. Так, обобщая известный результат о компактности диэдральных групп, мы доказываем компактность каждой группы, обладающей регулярной

абелевой подгруппой индекса 2 (теорема 6.13), и, с другой стороны, характеризуем компактные группы Фробениуса.

Теорема 6.18. Группа Фробениуса С < 8ут(К) компактна тогда и только тогда, когда | | = 2, и € V.

Далее мы полностью характеризуем компактные схемы Джонсона и компактные схемы ?г-мерного куба (теоремы 6.14 и 6.16). Из этого описания, в частности, следует некомпактность графа Петерсена, что отвечает на вопрос, поставленный Годсилом (1996). В завершение параграфа мы описываем все компактные схемы Платоновых тел (теорема 6.17).

Как уже говорилось выше, проблема изоморфизма компактных графов была решена в работах Тинхофера (1988,1991). В § 6.3 мы рассматриваем соответствующую проблему в классе компактных схем и в классе слабокомпактных графов. Ключевым моментом, обеспечивающим построение эффективных алгоритмов, является описание гп-орбит группы автоморфизмов компактной схемы в терминах клеток точечных расширений схем и подобий этих расширений (теорема 6.19). Здесь под подобием двух схем понимается биекция между множествами их базисных отношений, сохраняющая числа из (2). Используя алгоритм Вейсфейлера-Лемана для нахождения расширений и проверки их подобий, мы получаем следующий результат.

Теорема 6.20. Класс смежности всех изоморфизмов компактной схемы С по группе Аи^С), индуцирующих заданное подобие (р : С —► С, может быть найден за полиномиальное время от степени этой схемы. В частности, за то же время люжно найти группу Аи(;(С).

Применение этой теоремы к схемам слабокомпактных графов полностью решает проблему изоморфизма в этом классе.

Теорема 6.21. Изоморфизм двух п-вершинных слабокомпактных графов можно проверить за время га0'1).

Лесовидные схемы и алгебраические леса. Структура произвольной компактной схемы представляется сложной как с алгебраической, так и с комбинаторной точек зрения. В частности, кажется трудным построить эффективный алгоритм их распознавания. Поэтому мы выделяем и изучаем широкий подкласс компактных схем, называемых лесовидными (п. 6.4.1). Название становится ясным из предложения 6.32, показывающего, что каждая лесовидная схема совпадает с ограничением схемы некоторого леса. Исходное же определение конструктивно в том смысле, что согласно ему каждая лесовидная схема может быть получена из схемы степени один с помощью операций прямой суммы и сплетения се-

мейства подобных схем с симметрической группой (см. § 2.1 и п. 2.2.4). Анализ этих операций позволяет доказать, что класс лесовидных схем является отделимым, то есть что каждое подобие двух таких схем индуцируется некоторым изоморфизмом (теорема 6.23). Используя этот результат можно показать, что операция сплетения семейства подобных схем с симметрической группой в определении лесовидных схем может быть заменена простым сплетением со схемой ранга два. Отсюда в силу свойств компактных схем, изученных в предыдущих параграфах, следует, что все лесовидные схемы компактны (следствие 6.24). По теореме 6,4 это даёт следующее утверждение.

Теорема 6.25. Класс лесовидных схем туров.

Как было отмечено выше, понятие комбинаторной компактности возникло в связи с проблемой изоморфизма графов. Будучи сложной в классе всех графов, эта проблема может эффективно решаться для некоторых классов графов с ограниченной структурой. Многие из этих классов допускают чисто комбинаторные эффективные алгоритмы проверки изоморфизма., и среди них - хорошо известные классы деревьев, интервальных графов, кографов и даже графов ориентированных цепей (орцепей). Анализ этих результатов указывает на тесную связь между структурой этих графов и структурой обычных лесов. Мы вводим новый класс графов - алгебраические леса, определяющее свойство которых состоит в том, что их схемы являются лесовидными (п. 6.4.3), и доказываем, что все перечисленные выше классы обладают этим свойством.

Теорема 6.34, Kaotcduii граф орцепей является алгебраическим лесом.

(В доказательстве этого утверждения существенно используется теорема 6.29, показывающая, что схема произвольного несвязного графа изоморфна прямой сумме сплетений семейств схем с симметрической группой). Заметим, что класс алгебраических лесов значительно больше всех перечисленных выше, поскольку любой конечный граф является индуцированным подграфом некоторого алгебраического леса. С другой стороны, из нашего определения следует, что все алгебраические леса слабо компактны. Поэтому по теореме 6.21 изоморфизм двух алгебраических лесов можно проверить за полиномиальное время от числа вершин. Более того, рекурсивное определение класса лесовидных схем позволяет построить эффективный алгоритм их распознавания, который в совокупности с алгоритмом Вейсфейлера-Лемана обеспечивает доказательство следующей теоремы.

Теорема 6.38. По данному п-вершинному графу за время 0(п3 logn)

момсно проверить, является ли он алгебраическим лесом.

В качестве следствия наших результатов отметим тот факт, что размер полного множества инвариантов изоморфизма ?г-вершинного алгебраического леса не превосходит 0(п? \о£ п) (в качестве такого множества инвариантов может быть взят упорядоченный набор чисел, определяемых формулой (2) для соответствующей схемы).

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. I. Ponomarenko, Polynomial-time algorithms for recognizing and isomorphism testing of cyclic tournaments, Acta Appl. Math., 29 (1992), 139— 160.

2. I. Ponomarenko, Graph isomorphism problem and 2-closed permutation groups, Applicable Algebra in Engineering, Communication and Computing, 5 (1994), 9-22.

3. И. Пономаренко, Об одной оценке порядка примитивных групп перестановок, Записки научных семинаров ПОМП, 215 (1994), 256-263.

4. С. Евдокимов, И. Пономаренко, Транзитивные группы перестановок с представлениями ограниченной степени, Записки научных семинаров ПОМИ, 223 (1995), 108-119.

5. L. Babel, I. Ponomarenko, G. Tinhofer, The Isomorphism Problem for Directed Path Graphs and for Rooted Directed Path Graphs, J. of Algorithms, 21 (1996), 542-564.

6. С. Евдокимов, П. Пономаренко, О примитивных клеточных алгебрах, Записки научных семинаров ПОМИ, 256 (1999), 38-68.

7. S. Evdokimov, I. Ponomarenko, Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, Combinatorica, 19 (1999), 321-333.

8. S. Evdokimov, M. Karpinski, I. Ponomarenko, Compact cellular algebras and permutation groups, Discrete Mathematics, 197/198 (1999), 247-267.

9. S. Evdokimov, I. Ponomarenko, G. Tinhofer, Forestal algebras and algebraic forests (on a new class of weakly compact graphs), Discrete Mathematics, 225 (2000), 149-172.

10. S. Evdokimov, I. Ponomarenko, Two-closure of odd permutation group in polynomial time, Discrete Mathematics, 235/1-3, (2001), 221-232.

11. С. Евдокимов, И. Пономаренко, Распознавание и проверка изоморфизма цирк.улянтных графов за полиномиальное время, Алгебра и анализ, 15 (2003), 6, 1-34.

12. И. Пономаренко, Нахождение группы автоморфизмов циркулянтной ассоциативной схемы за полиномиальное время, Записки научных семинаров ПОМИ, 321 (2005), 251-267.

13. S. Evdokimov, I. Ponomarenko, A new 1оок at the Burnside-Schur theorem, Bulletin of the London Mathematical Society, 37 (2005), 535-546.

Подписано в печать 10.03.2006, Заказ №54388 Формат бумаги 60x84/16 Тираж 75 экз. Отпечатано в типографии «иШ-РШКТ» 19119, Санкт-Петербург, ул.Достоевского, 44. Тел./факс:: (812) 712-5814

Введение

1 Общая теория

1.1 Схемы отношений.

1.2 Алгебры смежности.

1.3 Группы перестановок.

1.4 Алгоритмы.

2 2-замыкания групп перестановок

2.1 Прямые суммы и тензорные произведения.

2.2 Сплетения групп и сплетения схем

2.3 Эксионенцирование схемы с группой перестановок.

2.4 Нахождение 2-замыканий в классах разрешимых групп.

3 Каноническая форма в классе всех схем

3.1 Линейные инварианты схем и групп.

3.2 Теорема Жордана и группы перестановок.

3.3 Канонические формы и канонические пометки

3.4 Основной алгоритм.

4 Теорема Бернсайда-Шура и её обобщение

4.1 Кольца Шура и схемы Кэли.

4.2 Кольца Шура над коммутативными кольцами.

4.3 Теорема о разделяющей подгруппе.

4.4 Доказательства теорем 4.11 и 4.8.

5 Канонические формы циркулянтных схем

5.1 Квазинормальные и сингулярные схемы.

5.2 Структура циркулянтных схем.

5.3 Циклическая база разрешимой группы.

5.4 Распознавание циркулянтных схем

5.5 Проверка изоморфизма циркулянтных графов

6 Теорема Биркгофа для схем и групп

6.1 Комбинаторная компактность.

6.2 Примеры компактных схем, групп и графов.

6.3 Алгоритм проверки изоморфизма компактных схем

6.4 Лесовидные схемы и алгебраические леса

В своей известной монографии "Геометрическая алгебра"М.Артин на стр.79 пишет: "В современной математике исследование симметрии данной математической структуры приводит, как правило, к наиболее значительным результатам". Поскольку значительная часть математических структур может быть определена в терминах отношений (различной арности), естественно изучать группы автоморфизмов семейств отношений. Такой подход впервые возникает у Галуа, который фактически определяет группу уравнения, как группу автоморфизмов семейства отношений на множестве его корней. По сути тот же подход используется и в работе Шура [71], в которой он обобщает теорему Бернсайда о примитивных группах перестановок с регулярной циклической подгруппой посредством изучения бинарных отношений, инвариантных относительно последней. Алгебраическим аналогом возникающих при этом комбинаторных структур и являются кольца, известные теперь как кольца Шура. Систематическое использование этого подхода было начато Виландтом в [79] и привело к появлению метода инвариантных отношений, сутыо которого и является изучение произвольных групп, как групп автоморфизмов подходящих семейств отношений. Уже в случае бинарных отношений этот метод позволил получить характеризацию некоторых групп ранга 3 [48] и построить ряд спорадических простых групп таких, например, как группа Хигмана-Симса.

Общая теория семейств бинарных отношений, наследующих свойства бинарных инвариантных отношений групп перестановок, была заложена в работе Хигмана [49] и, независимо, в работе Вейсфейлера и Лемана [4] (см. ниже). Такие семейства были названы когерентными конфигурациями, более современное название которых - ассоциативные схемы или просто схемы - связано с появлением монографий [1, 29, 81]. Среди наиболее впечатляющих применений теории схем отметим отметим классическую теорему Бабаи, дающую асимптотически точную оценку максимального порядка примитивной группы перестановок, не являющейся дважды транзитивной [21].

Одной из наиболее важных задач математики является нахождение полного множества инвариантов изоморфизма объектов заданной категории. В случае конечных объектов такое множество всегда может быть выбрано конечным и потому естественная проблема состоит в поиске наименьшего количества инвариантов. С алгоритмической точки зрения проблема изоморфизма заключается в оценке сложности наиболее эффективного алгоритма, проверяющего изоморфизм двух заданных объектов. Известно, что проблема изоморфизма конечных алгебраических структур сводится к проблеме изоморфизма конечных графов, являющейся одной из наиболее известных нерешённых проблем теории сложности вычислений [11, 22, 24]. Именно эта проблема привела Вейсфейлера и Лемана к открытию клеточных алгебр, которые есть ни что иное как алгебры смежности схем отношений [4]. Связав с каждым графом клеточную алгебру, порождённую его матрицей смежности, они фактически показали, что проблема изоморфизма графов полиномиально эквивалентна проблеме нахождения группы автоморфизмов схем отношений [77]. Эти идеи в дальнейшем были развиты в ряде работ [14, 67, 27, 35, 36].

Основной целью диссертации является исследование групп автоморфизмов ассоциативных схем как с сугубо теоретической, так и с алгоритмической точек зрения. Ключевым моментом здесь служит соответствие Галуа между множеством всех схем С на конечном множестве V и множеством всех подгрупп Г симметрической группы

Sym(K), задаваемое отображениями

С Aut(C), Г^1пу(Г), (1) где Aut(C) - группа автоморфизмов схемы С и Inv(r) - схема орбит группы Г относительно её индуцированного действия на V2. Замкнутыми объектами в этом соответствии являются шуровы схемы и 2-замкнутые группы. Следует отметить, что соответствие (1), не являясь взаимно-однозначным, становится таковым при некоторых условиях. Важный пример такой ситуации возникает для классов схем и групп, для которых справедлив аналог теоремы Биркгофа о дважды стохастических матрицах; мы развиваем соответствующую теорию в главе б. Правая часть соответствия (1) легла в основу метода Шура, применяемого к схемам, группа автоморфизмов которых содержит регулярную подгруппу. Накладывая на такие схемы условие инвариантности относительно автоморфизмов этой подгруппы, удаётся существенно обобщить известную теорему Бернсайда-Шура о группах перестановок (глава 4).

С вычислительной точки зрения можно легко найти схему группы эффективным алгоритмом, в то время как нахождение группы автоморфизмов - трудная задача, полиномиально эквивалентная проблеме изоморфизма графов. Эта задача упрощается, если известна некоторая априорная информация о группе автоморфизмов или её можно получить изучая структуру соответствующей схемы. В первом случае примером является долгое время остававшаяся нерешённой проблема нахождения эффективного алгоритма построения группы автоморфизмов циркулянтной схемы (у такой схемы группа автоморфизмов содержит регулярную циклическую подгруппу). Мы полностью решаем эту проблему в главе 5 значительно развивая теорию таких схем, построенную в последнее время [52, 9]. Во втором случае, используя известную теорему Жордана о линейных группах, мы доказываем, что группа автоморфизмов произвольной однородной схемы содержит разрешимую подгруппу, индекс которой ограничен некоторой функцией, зависящей от инвариантов линейных представлений алгебры смежности этой схемы. Это позволяет построить алгоритм для нахождения канонической формы и группы автоморфизмов в классе всех схем, работающий полиномиальное время, когда упомянутые инварианты растут медленно в сравнении со степенью схемы (глава 3).

Диссертация состоит из б глав, к изложению основных результатов которых мы и переходим.

1. Э. Баниаи, Т. Ито, Алгебраическая комбинаторика. Схемы отношений, М.: Мир, 1987.

2. Г. Биркгоф, Теория решёток, М.: Наука, 1984.

3. Г. Вейль, Классические группы. Их инварианты и представления, М.: ИЛ, 1947.

4. Б. Ю. Вейсфейлер, А. А. Леман, Приведение графа к каноническому виду и воз-никаюшая при этом алгебра, НТИ, сер. 2, 1968, 9, 12—16.

5. С. Евдокимов, Шуровостъ и отделимость ассоциативных схем, Диссертация на соискание степени д.ф.м.н., 2005, Санкт-Петербург.

6. С. Евдокимов, И. Пономаренко, Транзитивные группы перестановок с представлениями ограниченной степени, Записки научных семинаров ПОМИ, 223 (1995), 108-119.

7. С. Евдокимов, И. Пономаренко, О примитивных клеточных алгебрах, Записки научных семинаров ПОМИ, 256 (1999), 38-68.

8. С. Евдокимов, И. Пономаренко, Об одном семействе колец Шура над конечной циклической группой, Алгебра и анализ, 13 (2001), 3, 139-154.

9. С. Евдокимов, И. Пономаренко, Характеризация циклотомических схем и нормальные кольца Шура над циклической группой, Алгебра и анализ, 14 (2002), 2, 11-55.

10. С. Евдокимов, И. Пономаренко, Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время, Алгебра и анализ, 15 (2003), 6, 1-34.

11. В. Н. Земляченко, Н. М. Корнеенко, Р. И. Тышкевич, Проблема изоморфизма графов, Теория сложности вычислений, I. Записки научных семинаров ЛОМИ, 118 (1982), 83-158.

12. К. Кэртис, И. Райнер, Теория представлений конечных групп и ассоциативных алгебр, М., 1969.

13. А. А. Леман, Об автоморфизмах некоторых классов графов, Автоматика и Телемеханика, 2 (1970), 75-82.

14. И. Пономаренко, Проблема изоморфизма для классов графов, Докл. АН СССР, 304 (1989), 3, 552-556.

15. И. Пономаренко, Об одной оценке порядка примитивных групп перестановок, Записки научных семинаров ПОМИ, 215 (1994), 256-263.

16. И. Пономаренко, Нахождение группы автоморфизмов циркулянтной ассоциативной схемы за полиномиальное время, Записки научных семинаров ПОМИ, 321 (2005), 251-267.

17. Д. А. Супруненко, Группы матриц, М.: Наука, 1972.

18. В. 3. Файнберг, Группы автоморфизмов деревьев, ДАН БССР, 13 (1969), 10651067.

19. А. V. Aho, J. Е. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms,• Addison-Wesley, 1974.

20. A. Astie, Vertex-symmetric tournaments of order n with the minimum number of arc orbits, in: M. Fiedler (Edr), Recent Advances in Graph Theory, Academia, Prague, 1975, 17-30.

21. L. Babai, On the order of uniprimitive permutation groups, Annals of Math., 113 (1981), 553-568.

22. L. Babai, Automorphism groups, isomorphism, reconstruction, in: Handbook of combinatorics. Volume 2, edited by R. L. Graham, M. Grotschel and L. Lovasz, (Elsevier Science) 1995, 1447-1541.

23. L. Babai, D. Yu. Grigoryev, D. M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proc. 14th ACM STOC, 1982, 310-324.

24. L. Babai, W. Kantor, E. M. Luks, Computational complexity and the classification of finite simple groups, Proc. 24th Ann. Symp. Found. Comput. Sci, 1983, 162-171.

25. L. Babai, E. M. Luks, Canonical labeling of graphs, Proc. 15th ACM STOC, 1983, 171-183.

26. L. Babel, I. V. Chuvaeva, M. Klin, D. V. Pasechnik, Algebraic combinatorics in mathematical chemistry. Methods and Algorithm. II. Program implementation of the Weisfeiler-Leman algorithm,

27. L. Babel, I. Ponomarenko, G. Tinhofer, The Isomorphism Problem for Directed Path Graphs and for Rooted Directed Path Graphs, J. of Algorithms, 21 (1996), 542-564.

28. K. Booth, G. Lueker, A linear time algorithm for deciding interval graph isomorphism, J. of ACM, 26 (1979), 183-195.

29. A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-regular graphs, Springer, Berlin, 1989.

30. W. Burnside, Theory of Groups of Finite Order, 2nd ed. Cambridge: Cambridge Univ. Press, 1911.

31. P. J. Cameron, Homogeneous Cayley objects, Europ. J. Combinatorics, 21 (2000), 745-760.

32. A. Chan, C. D. Godsil, Symmetry and Eigenvectors, Graph symmetry (Montreal, PQ, 1996), 75-106, NATO Adv. Sci. Inst. Ser. С Math. Phys. Sci., 497, Kluvver Acad. Publ., Dordrecht, 1997.

33. D. G. Corneil, H. Lerch and L. Stewart, Complement Reducible Graphs, Discrete Appl. Math., 3 (1981), 163-185.

34. J. D. Dixon, B. Mortimer, Permutation groups, Graduate Texts in Mathematics, No. 163, Springer-Verlag New York, 1996.

35. S. Evdokimov, I. Ponomarenko, On the geometric graph isomorphism problem, Journal of Pure and Applied Algebra, 117 & 118, (1997), 253-276.

36. S. Evdokimov, I. Ponomarenko, Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, Combinatorica, 19 (1999), 321-333.

37. S. Evdokimov, I. Ponomarenko, On highly closed cellular algebras and highly closed isomorphisms, Electronic J. of Combinatorics, 6 (1999), #R18.

38. S. Evdokimov, I. Ponomarenko, Two-closure of odd permutation group in polynomial time, Discrete Mathematics, 235/1-3, (2001), 221-232.

39. S. Evdokimov, I. Ponomarenko, A new look at the Burnside-Schur theorem, Bulletin of the London Mathematical Society, 37 (2005), 535-546.

40. S. Evdokimov, M. Karpinski, I. Ponomarenko, On a New High Dimensional Weisfei-ler-Leman Algorithm, J. of Algebraic Combinatorics, 10 (1999), 29-45.

41. S. Evdokimov, M. Karpinski, I. Ponomarenko, Compact cellular algebras and permutation groups, Discrete Mathematics, 197/198 (1999), 247-267. (This paper has been selected for Discrete Mathematics Editor's Choice, 1999)

42. S. Evdokimov, I. Ponomarenko, G. Tinhofer, Forestal algebras and algebraic forests (on a new class of weakly compact graphs), Discrete Mathematics, 225 (2000), 149172.

43. I. A. Faradzev, M. H. Klin, M. E. Muzychuk, Cellular rings and groups of automorphisms of graphs, in: I.A. Faradzev et al. (eds): Investigations in algebraic theory of combinatorial objects, Kluwer Acad. Publ., Dordrecht, 1994, 1-152.

44. C. D. Godsil, Compact Graphs and Equitable Partitions, Linear Algebra Appl., 255 (1997), 259-266.

45. R. W. Goldbach, H. L. Claasen, Cyclotomic schemes over finite rings, Indag. Math. (N.S.), 3 (1992), 301-312.

46. M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

47. A. Hanaki, I. Miyamoto, Classification of primitive association schemes of order up to 22, Kyushu J. Math., 54 (2000), 81-86.

48. D. G. Higman, Characterization of families of rank 3 permutation groups by the subdegree I, II, Arch. Math., 21 (1970), 151-156; 353-361.

49. D. G. Higrnan, Coherent configurations 1., Rend. Mat. Sem. Padova, 44 (1970), 1-25.

50. I. M. Isaacs, Irreducible constituents of faithful induced characters, Proc. Amer. Math. Soc., 128 (2000), 3471-3474.

51. I. M. Isaacs, D. S. Passman, Groups with representations of bounded degree, Canad. J. Math., 16 (1964), 299-304.

52. К. H. Leung, S. H. Man, On Schur Rings over Cyclic Groups, II, J. of Algebra, 183 (1996), 273-285.

53. С. H. Li, On isomorphisms of finite Cayley graphs a survey, Discrete Mathematics, 256 (2002), 301-334.

54. С. H. Li, The finite primitive permutation groups containing an abelian regular subgroup, Proc. London Math. Soc., 87 (2003), 725-747.

55. A. Lubivv, Some NP-complete problems similar to graph isomorphism, SIAM J. Comput., 10 (1981), 11-21.

56. E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Сотр. Sys. Sci., 25 (1982), 42-65.

57. E. M. Luks, Permutation groups and polynomial-time computation, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11 (1993), 139-175.

58. R. Mathon, A note on the graph isomorphism counting problem, Inform. Process. Lett., 8 (1979), 131-132.

59. B. R. McDonald, Finite rings with identity, Pure and Applied Mathematics, Vol. 28, Marcel Dekker Inc., New York, 1974.

60. M. E. Muzychuk , On the structure of basic sets of Schur rings over cyclic groups, J. of Algebra, 169 (1994), 655-678.

61. M. Muzychuk, On the isomorphism problem for cyclic combinatorial objects, Discrete Math., 197/198 (1999), 589-606.

62. M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc., 88 (2004), 1-41.

63. M. Muzychuk, M. Klin, R. Poschel, The isomorphism problem for circulant graphs via Schur ring theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 56 (2001), 241-264.

64. M. E. Muzychuk, G. Tinhofer, Recognizing circulant graphs of prime order in polynomial time, Electronic J. of Combinatorics, 5 (1998), #R25.

65. M. E. Muzychuk, G. Tinhofer, Recognizing circulant graphs in polynomial time: An application of association schemes, Electronic J. of Combinatorics, 8, (2001), #R26.

66. P. P. Palfy, A polynomial bound for the orders of primitive solvable groups, J. of Algebra, 77 (1982), 127-137.

67. I. Ponomarenko, Polynomial-time algorithms for recognizing and isomorphism testing of cyclic tournaments, Acta Appl. Math., 29 (1992), 139-160.

68. I. Ponomarenko, Graph isomorphism problem and 2-closed permutation groups, Applicable Algebra in Engineering, Communication and Computing, 5 (1994), 9-22.

69. L. Pyber, How abelian is a finite group?, in: The Mathematics of Paul Erdos, Vol. I. (R. L. Graham et al. eds.), Algorithms and Combinatorics 13, Springer-Verlag, Berlin, 1997, 372-384.

70. H. Schreck and G. Tinhofer, A note on certain subpolytopes of the assignment polytope associated with circulant graphs, Linear Algebra Appl., Ill, (1988), 125-134.

71. I. Schur, Ziir Theorie der einfach transitiven Permutationgruppen, S.-B. Preus Akad. Wiss. Phys.-Math. Kl., (1933), 598-623.

72. A. Seress, The minimal base size of primitive solvable permutation groups, J. London Math. Soc., 53 (1996), 243-255.

73. A. Seress, Permutation group algorithms, Cambridge Tracts in Mathematics 152, Cambridge University Press, 2003.

74. G. Tinhofer, Graph isomorphism and theorems of Birkhoff type, Computing, 36, (1986), 285-300.

75. G. Tinhofer, Strong tree-cographs are Birkhoff graphs, Discrete Applied Math., 22, (1988/89), 275-288.

76. G. Tinhofer, A note on compact graphs, Discrete Applied Math., 30, (1991), 253-264.

77. B. Weisfeiler (editor), On construction and identification of graphs, Springer Lecture Notes, 558, 1976.

78. H. Wielandt, Finite permutation groups, Academic press, New York London, 1964.

79. H. Wielandt, Permutation groups through invariant relations and invariant functions, Lect. Notes Dept. Math. Ohio St. Univ., Columbus, 1969.

80. P.-H. Zieschang, Algebraic Approach to Association Schemes, Springer, Berlin к Heidelberg, 1996.

81. P.-H. Zieschang, Theory of Association Schemes, Springer Monographs in Mathematics, 2005.