КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

Номер 22-71-00021

НазваниеКольца Шура и проблема изоморфизма графов Кэли: теория и алгоритмы.

РуководительРябов Григорий Константинович, Кандидат физико-математических наук

Организация финансирования, регион федеральное государственное бюджетное образовательное учреждение высшего образования "Новосибирский государственный технический университет", Новосибирская обл

Период выполнения при поддержке РНФ 07.2022 - 06.2024 

Конкурс№70 - Конкурс 2022 года «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными.

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-114 - Дискретная математика и математическая кибернетика

Ключевые словаГраф Кэли, проблема изоморфизма графов, вычислительная сложность, алгоритм Вейсфейлера-Лемана, WL-размерность, когерентная конфигурация, шуровость, отделимость, кольцо Шура, группа Шура, абелева группа, группа перестановок, регулярная группа, суперхарактер.

Код ГРНТИ27.00.00

СтатусЗакрыт досрочно

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Проблема изоморфизма графов - это фундаментальная проблема математики и computer science, которая состоит в нахождении наиболее эффективного алгоритма проверки изоморфизма двух данных конечных графов. Эта проблема возникает в широком ряде задач хемоинформатики и математической химии, криптографии, оптимизации программ, математической лингвистике и тд. Несмотря на значительные усилия многих математиков в последние десятилетия, к настоящему моменту неизвестно разрешима ли проблема изоморфизма графов за полиномиальное время или является NP-полной. Прорывом в этой области стал алгоритм Бабаи (2016), решающий проблему изоморфизма графов за квазиполиномиальное время. Основными составляющими этого алгоритма являются теория групп перестановок, когерентные конфигурации и эффективные алгоритмы для групп и графов. Настоящий проект направлен на изучение проблемы изоморфизма графов Кэли, т.е. графов, группы автоморфизмов которых содержат регулярную подгруппу, и связанных с ней проблем. Особый интерес проблеме изоморфизма графов Кэли придаёт тот факт, что к ней сводится известная и широко изучаемая проблема изоморфизма групп. Отметим, что даже в случае графов Кэли известно не так много результатов об эффективном решении проблемы изоморфизма. Наиболее заметным среди таких результатов является полиномиальное решение проблемы изоморфизма циркулянтов, т.е. графов Кэли над циклическими группами, которое было получено независимо в работах Евдокимова и Пономаренко (2003) и Музычука (2004). Результаты об эффективном решении проблемы изоморфизма графов Кэли над некоторыми абелевыми группами были получены в серии работ Неделы-Пономаренко и Рябова (2018-2020). В рамках настоящего проекта планируется построить алгоритм проверки изоморфизма графов Кэли над абелевой группой порядка n и ранга r за время n^O(r). Ожидаемый результат является существенным продвижением в решении проблем изоморфизма графов Кэли и групп и обобщает ранее известные результаты о решении этих проблем. Одной из основных составляющих квазиполиномиального алгоритма Бабаи являются когерентные конфигурации, появившиеся в работах Вейсфейлера и Лемана (1968) и Хигмана (1970). По заданному графу с помощью алгоритма Вейсфейлера-Лемана может быть эффективно построена когерентная конфигурация, имеющая ту же группу автоморфизмов, что и исходный граф. Когерентная конфигурация называется шуровой, если она происходит из подходящей группы перестановок. Хорошо известно, что проблема изоморфизма графов полиномиально эквивалентна проблеме нахождения орбит группы автоморфизмов заданной когерентной конфигурации. Однако, если когерентная конфигурация шурова, то последняя проблема становится тривиальной. Когерентные конфигурации, построенные из графов Кэли, могут быть описаны на языке специальных подколец группового кольца - колец Шура (S-колец). Понятие S-кольца возникло в классических работах Шура и Виланда. Шур полагал, что каждое S-кольцо происходит из подходящей группы перестановок, т.е. шурово в современных терминах. Однако, это предположение было опровергнуто Виландом. В 1970е Пёшель ввел понятие группы Шура, т.е. такой конечной группы, каждое S-кольцо над которой является шуровым. Им же была предложена проблема определения всех групп Шура. В качестве одного из основных результатов проекта предполагается получить полную классификацию абелевых групп Шура. Отметим, что к настоящему моменту известно крайне мало результатов, касающихся S-колец над неабелевыми группами. Более того, неизвестно ни одного примера бесконечной серии неабелевых групп Шура. Попытки построить такую серию зачастую приводят к трудным проблемам теории чисел, в частности, к проблеме существования разностных множеств. Одним из немногих результатов об S-кольцах на неабелевыми группами является доказательство того, что классическая теорема Шура о мультипликаторах верна для центральных S-колец над произвольной группой (Чен-Музычук-Пономаренко, 2015). В рамках работ по проекту предполагается развить их подход с целью изучения S-колец над неабелевыми группами. Планируется ввести понятие обобщенной группы Шура, т.е. такой конечной группы, все центральные S-кольца над которой шуровы, и построить первые бесконечные серии таких групп. Помимо этого, планируется изучить S-кольца над нильпотентными группами и показать, что каждая нильпотентная группа Шура принадлежит одному из явно заданных бесконечных семейств групп. Конечная группа называется отделимой (в смысле S-колец), если каждое S-кольцо над этой группой отделимо, т.е. определяется с точностью до изоморфизма тензором своих структурных констант. Вопрос об отделимости S-колец является частным случаем общего вопроса комбинаторики о том, когда комбинаторная структура определяется своими параметрами. Если группа является отделимой, то проблема изоморфизма для графов Кэли над этой группой может быть решена за полиномиальное время с помощью алгоритма Вейсфейлера-Лемана. В рамках проекта предполагается получить полную классификацию отделимых абелевых групп и решить проблему изоморфизма для графов Кэли над ними за полиномиальное время.

Ожидаемые результаты
1. Получить классификацию абелевых групп Шура. Предполагаемый результат полностью решит проблему Пёшеля (1974) для абелевых групп, которая на протяжении 40 лет изучалась в работах Клина, Гольфанада, Наймарка, Евдокимова, Ковача, Пономаренко и др. Результат будет интересен как с алгебраической, так и с комбинаторной точки зрения и внесет существенный вклад в развитие теорий S-колец и групп перестановок. Помимо этого, он послужит основой для получения практических результатов о решении проблемы изоморфизма графов Кэли над абелевыми группами. 2. Доказать, что каждая нильпотентная группа Шура принадлежит одному из явно заданных бесконечных семейств групп. 3. Ввести понятие обобщенной группы Шура, построить бесконечные серии таких групп и развить теорию S-колец над неабелевыми группами. Ожидаемые результаты 2 и 3 касаются практически неизученной области - теории S-колец над неабелевыми группами. Предполагается, что они внесут существенный вклад в развитие этой теории и послужат основой для дальнейших исследований в области S-колец и графов Кэли над неабелевыми группами, в частности, для решения проблемы изоморфизма. 4. Получить классификацию абелевых отделимых (в смысле S-колец) групп. Решить проблему изоморфизма графов Кэли над этими группами за полиномиальное время. Предполагаемый результат ответит на классический вопрос комбинаторики о том, когда комбинаторная структура определяется своими параметрами, для S-колец над абелевыми группами. Кроме того, этот результат тесно связан с понятием WL-размерности графа, введенным Грое в 2017 и широко изучаемым в настоящее время в теории вычислительной сложности. Из ожидаемого результата будет следовать, что WL-размерность графов Кэли над отделимыми абелевыми группами не превосходит 2, а значит проблема изоморфизма для них может быть решена эффективно с помощью применения классического алгоритма Вейсфейлера-Лемана. 5. Решить проблему изоморфизма для графов Кэли над абелевой группой порядка n и ранга r за время n^O(r). В случае абелевых групп фиксированного ранга предполагаемый алгоритм для решения проблемы изоморфизма будет иметь полиномиальную сложность. Ожидаемый результат обобщит все известные результаты о решении проблемы изоморфизма графов Кэли над абелевыми группами, в частности, широко известные результаты Евдокимова-Пономаренко и Музычука о полиномиальном решении проблемы изоморфизма циркулянтов. Планируемый результат внесет существенный вклад в развитие как теории вычислительной сложности, так и алгебраической комбинаторики. Все ожидаемые результаты являются новыми и соответствуют мировому уровню. Они внесут существенный вклад в алгебраическую комбинаторику, теорию вычислительной сложности, теорию групп. Более того, они имеют важные приложения и приведут к появлению новых алгоритмов в прикладной теории графов и алгебраической комбинаторике, что в свою очередь приведёт к прогрессу в развитии современных цифровых технологий.

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Аннотация результатов, полученных в 2022 году
В 2022-2023 гг. одной из главных проблем, изучавшихся в рамках проекта, была проблема шуровости для S-колец и групп, являющаяся одной из краеугольных проблем алгебраической комбинаторики. Напомним, что S-кольцо над группой G - это подкольцо целочисленного группового кольца, наятнутое на специальное разбиение группы G. Понятие S-кольца тесно связано с графами Кэли, группами перестановок и представлениями конечных групп, т.е. находится на стыке нескольких областей математики. Шур в своей классической работе (1933) высказал предположение, что каждое S-кольцо может быть построено из группы перестановок. Однако, как позднее показал Виланд в своей монографии (1962) это не так. Позднее Пёшель ввёл (1974) следующие понятия. S-кольцо называется шуровым, если оно определяется подходящей группой перестановок, а конечная группа называется группой Шура, если каждое S-кольцо над этой группой шурово. В этой же работе Пёшель сформулировал проблему определения всех групп Шура, которая изучается в алгебраической комбинаторике на протяжении более чем 45 лет. Помимо интереса с точки зрения алгебраической комбинаторики, результаты об S-кольцах в целом и о проблеме шуровости в частности представляют интерес с точки зрения вычислительных проблем для графов Кэли, а также характеров конечных групп. Например, с помощью результатов об S-кольцах над циклическими группами были решены эффективно проблемы изоморфизма, распознавания, поиска представлений Кэли для некоторых (Клин-Пёшель, 1978) и в конечном итоге для всех циркулянтов (Евдокимов-Пономаренко, 2003, Музычук, 2004). С другой стороны, в 2010 Хендриксон показал, что суперхарактеры, введенные Айзексом и Диаконисом (2008) для изучения представлений алгебраических групп тесно связаны со специальным классом S-колец - так называемыми центральными S-кольцами. В общем случае проблема шуровости выглядит крайне трудной. Дело в том, что для проверки шуровости группы необходиом получить полное описание S-колец над этой группой. Но число S-колец экспоненциально зависит от порядка группы и получить такое описание зачастую не удается. Например, оно не получено даже в случае элементарной абелевой группы ранга 2. Попытки получить описание S-колец над неабелевой группой зачастую сталкиваются с трудными нерешенными проблемами теории чисел. Отметим, что известно крайне мало реузультатов о проблеме шуровости для неабелевых групп. С другой стороны, неизвестно общих методов построения прямых конструкций нешуровых S-колец для доказательства того, что данная группа не является группой Шура. В рамках проекта было доказано, что каждая нильпотентная группа Шура принадлежит одному из непосредственно заданных семейств групп. Таким образом, проблема шуровости для всех нильпотентных групп была сведена к проблеме шуровости для конкретных (бесконечных) семейств групп. Полученный результат является одним из немногих результатов о шуровости неабелевых групп и может быть использован для дальнейших исследований в теории S-колец. Еще одной целью проекта в 2022-2023 гг. было развитие теории центральных S-колец над неабелевыми группами. Поскольку теория S-колец над неабелевыми группами практически неразвита, в ней нет индустриальных методов, как например, классические теоремы Шура о мультипликаторах для S-колец над абелевыми группами. В 2016 Музычуком, Пономаренко и Ченом было предложено изучать центральные S-кольца над неабелевыми группами. Этот подход оказался плодотворным. С помощью него удалось доказать фундаментальные утверждения, являющиеся аналогами классических теорем из абелевого случая. В рамках проекта был продолжен этот подход и предложено понятие обобщенной группы Шура, т.е. такой конечной группы, что все центральные S-кольца над ней шуровы. Были исследованы базовые свойства таких групп, построены примеры, доказаны утвереждения, в том числе обобщающие классические результаты о шуровости для абелевых групп. Полученные результаты представляют интерес с точки зрения теории S-колец, а также с точки зрения теории характеров, так как все результаты могут интерпретированы на языке суперхарактеров. Наконец, доказанные утверждения могут быть использованы при решении вычислительных задач для центральных графов Кэли над неабелевыми группами, построения эффективных алгоритмов и тд. Одним из основных результатов проекта в 2022-2023 гг. является полная классификация абелевых групп Шура. Первым результатом о шуровости абелевых групп является теорема Пёшеля о том, что циклические p-группы шуровы (1974). Практически все результаты о проблеме шуровости до 2010х годов касались абелевых групп. Лишь в 2013 году Евдокимов, Ковач и Пономаренко получили полную классификацию циклических групп Шура. В рамках проекта был сделан следующий существенный шаг в решении проблемы шуровости - получена полная классификация абелевых групп Шура. Помимо этого, показано, что для каждой абелевой группы Шура выполнено утверждение классической теоремы Леунга-Мана. Полученные при доказательстве теоремы описания S-колец над абелевыми группами могут быть использованы для дальнейшего решения вычислительных проблем для графов Кэли над абелевыми группами. Наконец, в ходе проекта был построен FPT-алгоритм для нахождения множества всех изоморфизмов между двумя цветными (раскрашенными по вершинам и дугам) турнирами, параметром которого является максимальная валентность цветного класса дуг. Напомним, что турнир - это ориентированный граф, полученный из полного неориентированного графа приданием направления каждому ребру. Из результата Бабаи (2016) вытекает, что изоморфизм турниров может быть проверен за квазиполиномиальное время, однако не было известно FPT-алгоритма (и тем более полиномиального) для проверки изоморфизма турниров. С другой стороны, полученный результат даёт частичный ответ на вопрос Бабаи и Лакса (1983) о существовании FPT-алгоритма проверки изоморфизма графов, параметром которого является максмальная валентность вершин графа. Отметим, что построенный алгоритм при фиксированном параметре является полиномиальным и может быть реализован на компьютере. Помимо этого, было построено несколько вспомогательных FPT-алгоритмов для вычислений в группах автоморфизмов раскрашенных турниров. По результатам работы проекта было подоготовлено и сдано в печать три статьи в журналы Q1-Q2 (Scopus), одна из которых была опубликована, одна принята в печать и одна находится на рецензии. Помимо этого были сделаны устные доклады на двух международных конференциях и на двух семинарах в научных организациях.

 

Публикации

1. Рябов Г.К. Об обобщенных группах Шура Алгебра и логика, - (год публикации - 2023)

2. Рябов Г.К. On nilpotent Schur groups Сибирские Электронные Математические Известия, том 19, №2, с. 1077-1087 (год публикации - 2022) https://doi.org/10.33048/semi.2022.19.086

3. - В НГТУ НЭТИ проводятся исследования по алгебраической комбинаторике и проблеме изоморфизма графов Новосибирский государственный технический университет (сайт), - (год публикации - )