Комбинаторно-алгебраические методы исследования дистанционно-регулярных графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Глава Г. Общие сведения о дистанционно-регулярных графах и их группах автоморфизмов

§ 1.1. Основные определения.

§ 1.2. Дистанционно-регулярные графы в комбинаторике

§ 1.3. Дистанционно-транзитивные графы в теории конечных групп

§ 1.4. Импримитивные графы.

§ 1.5. Условия реализуемости массивов пересечений

§ 1.6. Реберно-транзитивные графы.

Глава 2. Комбинаторные методы исследования

§ 2.1. Характеристические матрицы и их свойства

§ 2.2. Ограничение диаметра.

§ 2.3. Некоторые следствия из -теоремы.

§ 2.4. Алгоритм перечисления массивов пересечений дистанционно-регулярных графов.

§ 2.5. Приемы доказательства несуществования дистанционно-регулярных графов с заданным массивом пересечений

Глава 3. Алгебраические методы исследования

§ 3.1. Существование и единственность дистанционнотранзитивных графов.

§ 3.2. Связь а-транзитивности с дистанционной транзитивностью

§ 3.3. Вычисление длин орбит подгруппы в транзитивной группе подстановок

§ 3.4. Транзитивное расширение групп подстановок

Глава 4. Результаты исследования некоторых конкретных классов графов

§ 4.1. Автоморфные графы степени к ^13 и диаметра <1^5.

§ 4.2. Дистанционно-транзитивные графы степени 5, 6 и

§ 4.3. Примитивные представления неабелевых простых груш порядка меньше 10^.

§ 4.4. Автоморфные графы, допускающие sn в качестве группы автоморфизмов

Многие задачи прикладной, математики допускают естественную формулировку в терминах отношений над элементами соответствующих множеств. Это обуславливает широкое применение методов и результатов теории графов как в прикладных дисциплинах, так и в других разделах математики. При этом особую роль играют графы, обладающие богатой: симметрией, то есть большой группой, автоморфизмов. Среди таких графов выделяется класс так называемых дистанционно-транзитивных графов (д.т.г.) , группа автоморфизмов которых действует транзитивно на упорядоченных парах равноудаленных вершин. Являясь весьма нетривиальным, класс д.т.г. охватывает значительную часть графов, интересных как с прикладной, так и с теоретической точек зрения. Отметим лишь, что широко применяемые в теории алгебраических кодов схемы отношений Хэмминга и Джонсона представляют собой д.т.г.

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

При реализации первого подхода на графы обычно накладывается более слабое условие дистанционной регулярности, являющееся комбинаторной апцроксимавдей свойства дистанционной транзитивности. Граф называется дистанционно-регулярным Сц.р.г.) , если для любого в и любых вершин х, и , находящихся на расстоянии в , число таких вершин V , которые находятся на расстоянии г от вершины х и на расстоянии t от вершины и , является функцией лишь в,г и t (не зависит от конкретного выбора вершин х и и ); здесь 8,г и t - неотрицательные целые числа, не превосходящие диаметра графа.

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

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

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

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

К настоящему времени накоплена очень большая информация о д.т. г. Известно несколько десятков бесконечных серий таких графов и ряд исключительных примеров (см. обзоры [7о1 , [эз] ). Ситуация с д.т.г. во многом напоминает положение с конечными простыми группами, классификация которых, как полагают, близка к своему завершетом, что многие бесконечные серии д.т.г. связаны с определенными сериями простых групп; такая же связь имеется и между некоторыми исключительными примерами д.т.г. и спорадическими простыми группами. При этом особую роль играют автоморфные графы ( а.г. ) - д.т.г., группы автоморфизмов которых действуют примитивно на множестве вершин. В § 1.3. сделан новый, шаг в систематизации указанных связей.

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

Д.т.г., не являющиеся а.г., могут иметь только два типа систем импримитивности: двудольный и антиподальный, цричем каждая такая система описывается в терминах компонент связности графов путей длины з ,1 ^а^ а . Такое описание проводится исключительно в комбинаторных терминах, что позволяет говорить о примитивных и имприми-тивных д.р.г. без использования какой-либо информации об их группах автоморфизмов. По каждому имцримитивному д.р.г. естественным образом строится примитивный д.р.г. с меньшим числом вершин. Ввиду этого разумно первоначально описывать примитивные графы, а затем строить их всевозможные расширения. Методы построения расширений изложены в § 1.4, где, в частности, приведена полученная автором характериза-ция расширений: полных двудольных графов.

Исторически первые классификационные результаты в теории д.т.г. нию аналогия подкрепляется тем факсостоят в описании графов малой степени к . Для к=2 эта задача тривиальна, поскольку д.р.г. степени 2-это обычные многоугольники. В [51] Н.Биггс и Д.Смит получили полное описание д.т.г. степени 3. Оказалось, что существует ровно 12 таких графов. Несколькими годами позже Д.Смиту Е120-122] удалось описать все д.т.г. степени 4. Таких графов имеется 15. Н.Биггс [49] при исследовании а.г. степени к £13 и диаметра <1 £ 5 поставил вопрос о существовании одиннадцати а.г. с заданными наборами параметров. Полный ответ на этот вопрос, полученный независимо двумя коллективами [ю, II, 13,14] ( см, также обзор £22] ) и [б8,70,8б] , завершил описание а.г. в указанном диапазоне к и а . Идеи и методы, использованные при решении этой задачи Н.Биггса, явились основой общего подхода к классификации д.т.г., развиваемого в настоящей работе. Вклад автора в решение задачи Н.Биггса отражен в § 4.1.

Следует отметить, что в классе д.р.г. ситуация существенно сложнее. Так описаны лишь двудольные д.р.г. степени 3 [9б] и даже д. вопрос о конечности числа д.р.г. степени общего вида остается пока открытым. Общая же проблема классификации д.р.г. даже не представляется реальной:. В пользу этого говорит хотя бы тот факт, что, как показано в [юб] , для любой абстрактной, группы й существует сильно-регулярный граф» группа автоморфизмов которого изоморфна й . Однако есть надежда, что при достаточно большом значении диаметра д.р.г. устроены менее аморфно. На это указывает тот факт, что все д.р.г. бесконечного диаметра являются д.т.г. С см. § 2.3) . Принципиальный подход к исследованию д.р.г. большого диаметра дает доказываемые в настоящей работе st -теорема и следствия из нее. Ввиду этих результатов первостепенную важность приобретает проблема ограничения длины минимального нестягиваемого цикла, отличного от треугольника в д.р.г.

Каждому д.р.г. однозначно ставится в соответствие определенный набор параметров, называемый: массивом пересечений этого графа.

Массив пересечений является исключительно важной характеристикой д.р.г. Это объясняется следующим. Во-первых по массиву пересечений однозначно восстанавливается целый ряд других параметров графа. Во-вторых, известны настолько сильные условия, необходимые для существования графов с заданным массивом пересечений ( условия реализуемости [48,49]) , что, по крайней мере, для малых значений степени, большинству массивов пересечений, удовлетворяющих всем известным условиям реализуемости, действительно соответствуют д.р.г. В-третьих, хотя и имеются примеры неизоморфных графов с одним и тем же массивом пересечений, во многих случаях д.р.г. определяется своим массивом пересечений однозначно. Вывод новых условий реализуемости массивов пересечений является одним из центральных результатов настоящей работы.

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

Для осуществления первого этапа необходимо обосновать ограниченность диаметра возможного графа. В случае д.т.г. степени 3 и 4 решающую роль при ограничении диаметра сыграли результаты, доказывающие справедливость гипотезы Ч.К.Симса для к=3 и 4 . Напомним, что гипотеза Ч.К.Симса состоит в том, что порядок фиксатора точки в произвольной, примитивной группе подстановок, имеющей подстепень к , ограничен некоторой функцией :е(к). В недавно вышедшей работе [б4] справедливость этой гипотезы доказана по модулю классификации конечных простых групп, однако полученная при этом оценка неконструктивна. Отметим, что ограниченность диаметра д.т;г. степени к не следует автоматически из справедливости гипотезы Ч.К.Симса для этого к , и до последнего времени этот вопрос не был решен.

При исследовании вопроса об ограниченности диаметра д.т.г. степени кэ>5 автору удалось вывести новые условия реализуемости, которые мы в дальнейшем будем называть st-теоремой: С теорема 2.2.1 в настоящей, работе ) . Как прямое следствие st -теоремы были получены следующие результаты С см. § 2.3) .

Г. Ограниченность диаметра произвольного д.р.г. определенной: функцией его степени и длины минимального не стягиваемого цикла, отличного от треугольника.

2. Ограниченность диаметра д.т.г. некоторой: функцией его степени в предположении справедливости гипотезы Ч.К.Симса.

3. Ограниченность порядка группы автоморфизмов & д.т.г. величиной , где н - фиксатор некоторой: вершины в группе й .

4. Полное описание бесконечных, локально конечных, д.р.г.

Некоторые из отмеченных следствий: в более слабых формулировках были получены независимо. Так в [129-130] доказана ограниченность диаметра д.р.г. функцией, его степени к и обхвата § в случае, когда ё четно; в [б2] доказано второе следствие, но полученные оценки несколько слабее; в [юз] описаны бесконечные, локально конечные д.т.г. Заметим, что st-теорема носит существенно более общий характер, а при ее доказательстве не делалось никаких предположений относительно групп автоморфизмов рассматриваемых графов.

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

Для нахождения всех массивов пересечений, которые соответствуют д.р.г. степени к и удовлетворяют упомянутым, а также известным ранее условиям реализуемости был разработан алгоритм перечисления таких массивов на основе метода ветвей: и границ. Этот алгоритм кратко охарактеризован в § 2.4.

Д.т.г. являются, в частности, реберно-транзитивными графами. Такие графы обладают рядом свойств С см. § 1.6 ), некоторые из которых могут быть сформулированы в терминах массивов пересечений д.т.г. С см. § 3,2 ) • Это позволяет говорить об условиях реализуемости массивов пересечений дистанционно-транзитивными графами. Ряд таких условий был заложен в упомянутый алгоритм. Из них, в частности, следует справедливость гипотезы Ч.К.Симса душ групп автоморфизмов д.т.г. степени к<7 .

Корректность работы алгоритма была апробирована независимым перечислением массивов пересечений д.т.г. степени 3 и 4. Затем с помощью этого алгоритма удалось получить полный список массивов пересечений: д. т. г. степени 5, 6 и 7 С см. § 4.2 ) . Для всех найденных массивов были либо построены полные с точностью до изоморфизма наборы д.т.г., либо доказано несуществование таких графов. В частности, показано, что имеется в точности 14, 24 и 14 д.т.г. степени, соответственно, 5, 6 и 7. Среди построенных графов имеются новые, представляющие на наш взгляд самостоятельный интерес.

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

При наличии массива пересечений в ряде случаев удается установить конкретный вид характеристических матриц различных пар вершин. Рассмотрение таких матриц либо позволяет однозначно восстановить структуру графа, либо приводит к цротиворечию, что доказывает несуществование графов с рассматриваемым массивом пересечений. Соответствующие примеры приведены в § 2.5 и § 4.3. Однако в классе д.р.г. такой подход приводит к успеху далеко не всегда и здесь имеется большое количество открытых вопросов.

Ограничиваясь классом д.т.г., удается продвинуться значительно дальше. Здесь становится применима упомянутая методика установления связей между комбинаторной структурой возможного графа и свойствами его группы автоморфизмов.

Исходя из заданного массива пересечений., и, предполагая дистанционную транзитивность, удается получить верхнюю и нижнюю оценки на порядок возможной группы автоморфизмов С см. § 3.1) . Кроме того, в ряде случаев оказывается, что группа автоморфизмов д.т.г. с рассматриваемым массивом является простой группой, расширенной, быть может с помощью внешних автоморфизмов С лемма 3.1.12 ) . Используя оценки на порядок этой группы, а также многочисленные результаты характеризации конечных простых групп, часто оказывается возможным отождествить минимальный нормальный делитель в группе автоморфизмов возможного графа с некоторой известной, простой группой. В других случаях, исходя из массива пересечений удается получить достаточно полную информацию о строении фиксатора вершины в группе автоморфизмов возможного графа.

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

I. н - фиксатор вершины в группе автоморфизмов. Тогда приходим к задаче транзитивного расширения групп подстановок. Алгоритм решения этой задачи состоит в построении подкольца V-кольца группы н с заданными структурными константами и транзитивной группой автоморфизмов С см. § 3.4 ) . Существенную роль в сокращении перебора при поиске такого подкольца играет предложенный, автором метод неподвижных точек, который основан на рассмотрении различных подгрупп Р в Н , нахождение их неподвижных точек и восстановлении действия нормализатора г в искомой транзитивной, груше на этом множестве неподвижных точек. Теоретической основой: метода неподвижных точек является теорема Дж. Алперина [зэ] , обобщающая классические результаты К.Жордана.

В ряде случаев метод неподвижных точек позволяет решать задачу транзитивного расширения индуктивно и сразу душ целых серий групп. В таких ситуациях имеет смысл отойти от стандартной: схемы классификации и строить д.т.г., не задаваясь конкретным видом массива пересечений, а исходя лишь из информации о строении фиксатора вершины в группе автоморфизмов. На этом пути автором получено полное описание д.т.г. степени к , фиксатор вершины в группе автоморфизмов которых при действии на соседних вершинах содержит знакопеременную группу степени к С теорема 3.4.3) .

2. Н действует транзитивно на множестве вершин графа. При этом мы можем воспользоваться упомянутым соответствием Галуа в полном объеме, определить полную решетку подколец V-кольца группы н и выделить среди них подкольца, порожденные д.т.г.' Отметим, что на этом пути возникают д.р.г., не являющиеся д.т.г., но обладающие транзитивной на вершинах группой автоморфизмов;

При таком подходе мы также можем отойти от стандартной схемы и систематически исследовать подкольца V-колец транзитивных групп подстановок. Результаты такого рода деятельности для примитивных представлений: неабелевых простых групп порядка меньше ТО6 цриведе-ны в § 4.3. На этом пути было найдено шесть новых сильно-регулярных графов, представляющих самостоятельный интерес.

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

- -lc5 группе подстановок, в частности, ранга и подстепеней. Этот метод изложен в параграфе 3.3 и проиллюстрирован на примере одной, серии групп подстановок, абстрактно изоморфных группам PSL2(q). st -теорема и следствия из нее позволяют вплотную подойти к задаче описания д.т.г., группы автоморфизмов которых абстрактно изоморфны заданным группам из бесконечных серий. Для симметрических групп такая задача была поставлена Н.Биггсом в [50^ , общая постановка приведена в [22~] . Автору удалось получить полное описание а.г., допускающих симметрическую группу в качестве группы автоморфизмов. Оказалось, что все такие графы либо изоморфны графам Джонсона, либо строятся из этих графов при помощи стандартных операций.

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

Основные результаты диссертации опубликованы в работах [il,14,15,16,17,18,19,20,2l] .

Автор выражает глубокую признательность своему научному руководителю, доктору физико-математических наук профессору Ю.И.Журавлеву за большое внимание к работе; научному консультанту , кандидату физико-математических наук доценту М.Х.Клину за большое количество ценных советов, а также кандидату физико-математических наук И.А.Фараджеву за плодотворные обсуждения.

Заключение

В работе получены следующие новые результаты:

1. Разработан общий подход к исследованию дистанционно-регулярных графов, сочетающий, в себе применение как комбинаторных, так и алгебраических методов.

2. Получены новые комбинаторные условия реализуемости массивов пересечений дистанционно-регулярными графами (теорема 2.2.1). Как прямое следствие из этих условий, получены следующие результаты: а. Ограниченность диаметра дистанционно-регулярного графа определенной функцией его степени к и .длины в минимального не стягиваемого цикла, отличного от треугольника ( теорема 2.3.2 ). б. Конечность числа дистанционно-транзитивных графов заданной степени к в предположении справедливости гипотезы Ч.К.Сим-са( лемма 2.3.8 ). в. Ограниченность порядка группы автоморфизмов дистанционно-транзитивного графа кубом порядка фиксатора вершины в этой группе (теорема 2.3.9 ). г. Полное описание бесконечных, локально конечных дистанционно-регулярных графов ( теорема 2.3.10 ) , позволившее дать отрицательный ответ на вопрос Л.Бабаи - К.Годсила о существовании бесконечных, локально конечных дистанционно-транзитивных графов связности больше или равной двум.

3. Разработан метод вычисления длин орбит подгруппы в транзитивной. группе подстановок. Этот метод позволяет в ряде случаев решать вопрос о существовании дистанционно-регулярных графов, не проводя явного построения (см, § 3.3 ) .

4. Предложен алгоритм решения задачи транзитивного расширения на основе метода неподвижных точек. Этот алгоритм является мощным инструментом построения дистанционно-транзитивных графов с заданным массивом пересечений: ( см, § 3.4 ).

5. Решен вопрос о существовании ряда автоморфиных графов с заданными массивами пересечений, поставленный Н.Биггсом ( см. § 4.1).

6. Получено полное описание дистанционно-транзитивных графов степени 5, 6 и 7 ( см. § 4.2 и приложение I ).

7. Описаны все дистанционно-регулярные графы, инвариантные относительно примитивных представлений неабелевых простых групп пос рядка меньше 10 , отличных от групп серии рзь2^) , ранг которых не превосходит 30. Среди этих графов имеется шесть новых сильно-регулярных (см. § 4.3 и приложение 2 ).

8. Описаны все автоморфные графы, допускающие дистанционно-транзитивное действие симметрических групп зп ( теорема 4.4.11 ), что дает частичный ответ на вопрос Н.Биггса, касающийся дистанционно-транзитивных графов, группа автоморфизмов которых абстрактно изоморфна зп .

1. Зайченко В.А., Иванов A.A.,Клин М.Х. Построение и исследование некоторых новых автоморфных графов. Тезисы докладов II Всесоюзного совещания "Методы и программы решения оптимизационных задач на графах и сетях". 4.2. Новосибирск,1982, с. 48-50.

2. Зайченко В.А., Клин М.Х., Фарадкев И.А. О некоторых вопросах, связанных с представлением групп подстановок в памяти ЭВМ.- В сб.: Вычисления в алгебре, теории чисел и комбинаторике. Киев, Ж АН УССР, 1980, с. 21-32.

3. Иванов A.A. Построение с помощью ЭВМ некоторых новых автомодных графов.- В сб.: Аэрофизика и прикладная математика. М. МФТИ, 1981, с. 144-146.

4. Иванов A.A. Ограничение диаметра дистанционно-регулярного графа.- ДАН СССР, 1983, Т. 271, JÉ 4, с. 789-792.

5. Иванов A.A. Вычисление длин орбит подгруппы в транзитивной группе подстановок.- В кн.: Методы и программы исследования сложных систем. Труды конференции молодых ученых. М. ВНИИСИ,1983, с. 3-7.

6. Иванов A.A., Клин М.Х., Царанов C.B., Шпекторов C.B. К вопросу о вычислении подстепеней транзитивных групп подстановок.- УМН, 1983, вып. 6, т. 38, с. II5-II6.

7. Калужнин I.A., Сущанский В.И., Устименко В.А. Применение ЭВМ в теории групп подстановок и их приложениях.-Кибернетика, 1982, № 6, с. 83-94.

8. Камеров П., Линт Дж. ван. Теория графов, теория кодирования и блок-схемы« М., Наука, 1980.

9. Клин М.Х. О транзитивном расширении групп подстановок.- В кн. Всесоюзный алгебраический симпозиум /Гомель, 30 июня -2 июля 1975 г./. Тез. докладов, ч. I. Шнек, Наука и техника 1975. с. 24-25.

10. Мак-Вильямс Ф.Дж., Слоан Н.Дж.А. Теория кодов, исправляющих ошибки. М., Связь, 1979.

11. Медведев В.К., Устименко-Бакумовский: В.А. Транзитивные расширения групп подстановок.- В сб.: Группы подстановок и комбинаторные объекты. Препринт ИМ АН УССР, Г982, с. 52-57.

12. Погорелов Б.А. Примитивные группы подстановок малых степеней I.- Алгебра и логика, 1980, т. 19, $ 3, с. 348-379.

13. Погорелов Б.А. Примитивные группы подстановок малых степеней 2.- Алгебра и логика, 1980, т. 19, $ 4, с. 423-457.

14. Симе Ч.К. Вычислительные методы в изучении групп перестановок,- В кн.: Вычисления в алгебре и теории чисел. М. Мир, 1976, с. 129-148.зо