Комбинаторно-алгебраические методы исследования дистанционно-регулярных графов Иванов Александр Анатольевич

Содержание к диссертации

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1. Автоморфные графы степени к =13 и диаметра . 92

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

4.3. Примитивные представления неабелевых простых групп порядка меньше ТО6 102

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

Заключение 118

Литература 120

• Дистанционно-транзитивные графы в теории конечных групп
• Приемы доказательства несуществования дистанционно-регулярных графов с заданным массивом пересечений
• Вычисление длин орбит подгруппы в транзитивной группе подстановок
• Примитивные представления неабелевых простых групп порядка меньше ТО6

Введение к работе

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

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

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

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

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

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

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

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

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

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

Исторически первые классификационные результаты в теории д.т.г. состоят в описании графов малой степени к . Для к=2 эта задача тривиальна, поскольку д.р.г. степени 2-это обычные многоугольники. В [бі] Н.Биггс и Д.Смит получили полное описание д.т.г. степени 3. Оказалось, что существует ровно 12 таких графов. Несколькими годами позже Д.Смиту El20-I22j удалось описать все д.т.г. степени 4. Таких графов имеется 15. Н.Биггс [49] при исследовании а.г. степени к 13 и диаметра d 5 поставил вопрос о существовании одиннадцати а.г. с заданными наборами параметров. Полный ответ на этот вопрос, полученный: независимо двумя коллективами ю, 11,13,14] ( см, также обзор [22J ) и [58,70,86j , завершил описание а.г. в указанном диапазоне к и d . Идеи и методы, использованные при решении этой: задачи Н.Биггса, явились основой общего подхода к классификации д.т.г., развиваемого в настоящей работе. Вклад автора в решение задачи Н.Биггса отражен в § 4.1.

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

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

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

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

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

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

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

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

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

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

Некоторые из отмеченных следствий: в более слабых формулировках были получены независимо. Так в [l29-I30j доказана ограниченность диаметра д.р.г. функцией, его степени к и обхвата g в случае, когда g четно; в [62J доказано второе следствие, но полученные оценки несколько слабее; в [l03J описаны бесконечные, локально конечные д.т.г. Заметим, что st-теорема носит существенно более общий характер, а при ее доказательстве не делалось никаких предположений относительно групп автоморфизмов рассматриваемых графов.

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

Для нахождения всех массивов пересечений, которые соответствуют д.р.г. степени к и удовлетворяют упомянутым, а также известным ранее условиям реализуемости был разработан алгоритм перечисления таких массивов на основе метода ветвей: и границ. Этот алгоритм крат -IO-KO охарактеризован в § 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-кольца (см., § Г.І ) , искомый граф ищем в виде подкольца в V-кольце группы Н . Здесь выделяются следующие два случая.

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

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

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

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

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

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

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

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

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

Подгруппу в называют борелевской подгруппой, а группу w группой Вейля. Мощность системы образующих S группы Вейля называется рангом (в,и) -пары.

Известно [132] , что в группе G , обладающей (в,Ю -парой любая подгруппа Р2 в однозначно определяет подмножество J с s таким образом, что Р Pj = BWjB , где Wj = j . Подгруппы Pj и сопряженные с ними в группе G называются параболическими. В случае группы PSLn(q) параболические подгруппы - это в точности стабилизаторы подпространств в Р , а для симплектической, ортогональной, и унитарной групп - это стабилизаторы подпространств Р , изотропных относительно соответствующей формы f .

Каждая группа типа Ли обладает (в,и) -парой. В своей фундаментальной работе [іЗЗ] Ж.Титс показал, что каждая группа с (B,N) -парой ранга =? 3 изоморфна группе типа Ли. Классификация (в,Ю -пар ранга 2 является одной из наиболее сложных проблем теории конечных групп. Представления многих групп, обладающих (в,її) -парой, на смежных классах по подходящей параболической подгруппе является представлением максимального диаметра, однако рассмотрение связей д.т.г. и (в,Ю -пар в общем виде выходит за рамки настоящей работы. Мы остановимся подробно лишь на (в,Ю -парах ранга 2. Лемма 1.3.3. Г73.86І Пусть G - группа с (в,и) -парой ранга 2 и группой Вейля w порядка 2d , порожденной инволюциями б И Т . Пусть [BUB $BJB] « s+1, [BUBtB:B] = t+1 . Тогда G действует на обобщенном d-угольнике с параметрами (s,t) t причем действие G на точечном графе и графе прямых дистанционно-транзитивно. Известные группы с (в,Ю -парами ранга 2 и параметры соответствующих обобщенных d -угольников приведены в таблице I.3.I, взятой из [92] . Описанные в этой таблице обобщенные d-угольники мы будем называть классическими. Однако не все известные обобщенные d-угольники соответствуют группам с (в,Ю -парами ранга 2, приведенным в таблице I.3.I. Примеры неклассических; обобщенных 4-угольников указаны в [98] . Как было отмечено в 1.2, графы инцидентностей обобщенных d-угольников с параметрами (t,t) являются (t+i,2d) -графами и играют важную роль в описании д.т.г., являющихся реберными графами. Из таблицы I.3.I мы получаем три серии таких примеров, связанных с группами A2(q), B2(q) и G2(q) . Комбинируя результаты [77J, теорему 1.8 из [84] , теорему 2 из [89] и утверждение 4.4 из [143], получаем характеризацию обобщенных d-угольников с параметрами (t,t). Лемма 1.3.4. Пусть S = (Р,В,1) - обобщенный: d-угольник с параметрами (t,t) t t l,d 2. Тогда d {3,4,6} , причем (і) если d=3 и граф инцидентностей s является д.т.г., то "Ь - РГ, р- простое; s - дезаргова проективная плоскость, т.е. s связан с группой типа А СР1). (ii) если d=4( d=6) , точечный: граф и граф прямых являются д.т.г., то t = рг и s связан с группой. B2(q) (G2(q)).

Точечный граф и граф прямых обобщенного d-угольника с параметрами (t,t) являются д.р.г. с одним и тем же массивом пересечений. Однако даже для классических обобщенных d -угольников изоморфизм между этими графами имеет место не всегда. Наличие такого изоморфизма эквивалентно сопряженности в Aut(G) двух классов максимальных параболических подгрупп соответствующей, группы G с (в,н) парой ранга 2. Эта сопряженность имеет место при всех q для групп типа A2(q) ( дезаргова проективная плоскость всегда самодвойственна ). Однако в случае групп B2(q) сопряженность имеет место лишь при q = 2Г, а в случае G2(q) - при q я зг[30,67] .

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

Недавно Ф.Бекенхут [5б] ввел класс так называемых диаграммных геометрий, являющийся обобщением класса параболических геометрий для групп типа Ли. К настоящему времени построены диаграммные геометрии для всех 26 известных спорадических простых групп [57,112"] Многие из этих конструкций описываются в терминах д.т.г., инвариантных относительно рассматриваемых групп.

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

В прикладной комбинаторике значительный интерес представляет изучение t-(v,k,% ) -схем [20,21,23] то есть таких совокупностей в подмножеств (называемых блоками) множества Р , состоящего из v точек, что каждое подмножество из В содержит к точек, а всякая система из t различных точек содержится ровно в подмножеств из в . Основной сферой; применения t-(v,k, \) -схем является теория планирования экспериментов. Хорошо известно, что каждая t -схема является (t-1) -схемой, для 2-схем используют термин блок-схема.

Пусть (Р,в) является симметричной 2-(v,k,X ) -схемой, т.е. Jpj = /ві в v . Построим граф Г инцидентностей схемы (Р,в) , в котором множество вершин есть v( г )=PL/B , а смежность соответствует включению точки в блок.

Лемма 1.2.7. Граф Г является д.р.г. с массивом пересечений (1.2.1) і(Г) = (k,k-1,k-A ;1,X,k} .И наоборот, любой д.р.г. с массивом (1.2.1) соответствует некоторой симметрической, 2-(v,k,A ) -схеме ( v = 1 + k(k-1)/X). Доказательство вытекает непосредственно из определений. Построенный таким образом граф Г является д.т.г. в точности тогда, когда блок-схема самодвойственна, ее группа автоморфизмов действует дважды транзитивно на множестве точек, а стабилизатор блока в группе автоморфизмов действует транзитивно как на множестве точек, входящих в этот блок, так и на его дополнении. Так, например, графы инцидентностей дезарговых проективных плоскостей являются д.т.г., и наоборот, плоскость дезаргова, если ее граф инцидентностей является д.т.г. другая серия д.р.г., связанных с проективными плоскостями, будут обсуждаться в 1.4. Следующее определение обобщает понятие проективной плоскости. Определение 1.2.8. [69J Линейной системой инцидентностей с параметрами (s,t) называется упорядоченная тройка s = (P,B,I) , где Р - множество точек, в - множество прямых, a ISPX в отношение инцидентности, которая удовлетворяет следующим условиям: (і) Каждая точка инцидентна ровно t+1 прямым и две различные точки инцидентны не более чем одной общей прямой. (ii) Каждая прямая инцидентна ровно s+1 точкам и две различные прямые инцидентны не более чем одной общей точке. Если Г - граф инцидентностей системы s , то v( Г) = рив, Е( Г) в і , Точечный граф системы s имеет в качестве вершин множество р , две вершины смежны, если соответствующие точки инцидентны общей прямой. Граф прямых определяется двойственно. Введенный Р.Боузом [бз] класс частичных геометрий (см. также [зз] ) также связан с д.р.г. Определение 1.2.9. Конечной частичной геометрией с параметрами (s,t,bL), oL t называется линейная система инцидентностей s = (Р,в,1) , в которой для каждой неинцидентной пары (р,1) ; существует ровно л точек Р.,,Р2 ...,Р и . прямых :ц,12,... 1 , таких что (p i i, (рд±)1, (РІ,І)ЄІ, Следующая лемма также вытекает из определений. Лемма 1.2.10. Граф инцидентностей частичной, геометрии с параметрами (t,t,ek) при . t+1 является д.р.г. с массивом пересечений (1.2.2) {t+1,t,t,t+1-cL;1,1, i,t+l} . И наоборот, любой д.р.г. с массивом (1.2.2) определяет частичную геометрию с параметрами (t,t,d.) Старая проблема теории графов о минимальном числе вершин регулярного графа степени к и обхвата g также сводится к изучению д.р.г. Лемма 1.2. II. [48] (і) В графе Г степени к и обхвата g= 2d+l не менее чем n0(k,g) = 1 + к + к(к-1) +... + k(k-1)(s 3"2 вершин. Если v( Г )\ n0(k,g) , то Г - д.р.г. диаметра d с массивом (1.2.3) {к,к-1,к-1,...,к-1;1,1,...,1} (іі) В графе Г степени к и обхвата g=2d не менее чем n0(k,g) ш 1 + к + к(к-1) + ... + k(k-1)(s"1;)/2+(k-1)s/2 вершин. Если v( Г )= nQ(k,g) , то Г - д.р.г. диаметра с массивом (1.2.4) {к,к-1,к-1,...,к-1;1,1,...,к} Определение 1.2.12. (k,g) -графом называется регулярный- граф степени к , обхвата g и имеющий, ровно nQ(k,g) вершин. (k,g) -графы нечетного обхвата называются графами Мура. Использование условий реализуемости массива (1.2.3) позволяет получить следующий результат. Лемма 1.2.13. [4в] Пусть Г - граф Мура степени к З и обхвата g 5 . Тогда g = 5, к е {з, 7, 57} . Заметим, что графы Мура при к =»2 это циклы нечетной .длины, а при g = 3 - полные графы. (3,5) -граф это нечетный граф О3 , известный также как граф Петерсена; (7,5) - граф - единственный [97J , является д.т.г. и называется графом Хоффмана-Синглетона. Вопрос о существовании (57,5) -графа до сих пор не решен, однако известно [41J , что такой граф не может быть д.т.г. (k,g) -графы четного обхвата мы рассмотрим в общем контексте так называемых обобщенных d -угольников. Определение 1.2.14. Обобщенным d-уголышком называется такая линейная система инцидентностей s = (Р, в, I) с параметрами (s,t), что (і) для каждой: пары х,ує PUB (х,у) dj (ii) если для х,ус PUB /9(x,y) d , то существует единственный; путь длины меньше d , соединяющий- х и у . Здесь расстояние измеряется в графе инцидентностей системы S . Заметим, что проективные плоскости это обобщенные 3-угольники. Лемма 1.2.15. [ІІЗ] Точечный граф и граф прямых обобщенного й-угольника являются д.р.г. диаметра [d/2] с массивом пересечений; (s(t+1 ),st,.. .,st;1,1,...,t+l} и {t(s+i),st,...,st;i,1,...,s+1} , соответственно. Если же s = t, то сам граф инцидентностей обобщенного d -угольника является д.р.г. диаметра d с массивом пересечений

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

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

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

Наиболее важной характеристикой, группы является ее порядок. Пусть Г - д.т.г., п я VCD I , (я действует дистанционно-транзи-тивно на Г, тогда IGJ = п«1с(х) для х є v(r) , Если массив пересечений і(Г) задан, то п известно и вопрос о порядке группы G сводится к оценке I G(x) .в ряде случаев по массиву і(Г) удается заключить, что G действует s-транзитивно на Г и оценить величину s . При этом результаты 1.6 позволяют получить верхнюю оценку на G(X)) . Нижняя оценка вытекает из транзитивности действия G(x) наГг(х), 1 r а .

Рассматривая действие G(x) на подграфах Гг(х) приходим к следующему утверждению: Демма 3.1.2 Для каждого 1 s.r s а определен гомоморфизм fr: G(x) —«- Aut( rr(x) ) . Ядро гомоморфизма fT составляет подгруппа Gr(x) , которая фиксирует множество Гг(х) поэлементно. Если Gr(x) = 1 , TOG(X)I делит Uut( rr(x) ) . Это имеет место в случае, когда G(x) действует точно на Гг(х) С этой точки зрения интересен следующий достаточный критерий точности действия G(x) на Гг(х) Лемма 3.1.3. Пусть Г - д.т.г. с массивом пересечений КГ), I и J - следующие множества индексов: I ={r l«r d-1, cr+1 h J U(di , J = {г j 1 r d , Ъг_., h } , где h=raax{a1, c максимально возможное число общих соседей двух различных вершин в графе Г. Тогда, если г є if)J , то G(x) действует точно на Гг(х). Доказательство. Покажем, что для rsi GJX) действует три-виально на Гъ(х) при t r . Так как последовательность {csj _1 монотонно неубывает, то включение гєі влечет tei для-ь г . Поэтому достаточно рассмотреть случай t = r+1 . Если Gr(x) действует нетривиально на Гг+1(х) , то найдется элемент geGr(x) такой.}что ys У для некоторой вершины у є Гг+1(х) . В этом случае, очевидно, Гг(х)П Г-,(у) = Гг(х)П Г у2) с Г., (у) О r.,(ys) и различные вершины У» ys имеют сг+1 общих соседей, - противоречие тому, что rei . Аналогично доказывается, что при r sJ G (х) действует тривиально на Г+(х) при t sr . Здесь мы поль , d-1 зуемся монотонностью последовательности lbg} g=1 . Опираясь на лемму 3.1.3, принципиально не удается обосновать : тривиальность подгруппы G x) . в то же время этот случай наиболее интересен и заслуживает особого внимания. Демма 3.1.4. Пусть G (x) действует тривиально на Г2(х) . Тогда Gt(x) = 1 . Доказательство. Предположим, что G,,(x) действует тривиально на Г (х) при t«r , но нетривиально на Г (х) , r 2 . Пусть у Гг+1(х) t z6r2(y)0rr-1(x). По предположению G1(x) G1(z) , значит G x) G2(x) и G1(x) G y), что противоречит нетривиальности действия G-j(x) на Гг+1(х).Ш Отметим, что в доказательстве леммы 3 1.4 существенна не дистанционная транзитивность Г, а лишь его связность и транзитивность действия G на V(r) Во многих случаях оказывается весьма полезна следующая несложная лемма: Лемма 3.1.5. Каждый ( абстрактный ) композиционный: фактор подгруппы G(x) присутствует среди композиционных факторов действий (Н, r-jCx)) , где H G(x) . Доказательство проводится аналогично доказательству теоремы 18.2 в IJ42J , причем требование примитивности действия (G,v(r)) следует заменить требованием связности графа Г.Щ Пусть Г - д.т.г., для которого с2 = 1 , тогда каждая клика К графа Г содержит ровно а1 + 2 вершин и каждая вершина входит ровно в m = k/(a.,+1) таких клик. Лемма 3.1.6. Подгруппа G(x) действует дважды транзитивно на кликах К-(зс),к2(х) , ...,Km(x) , содержащих х , а подгруппа G {к} , стабилизирующая клику К как множество, действует дважды транзитивно на вершинах, входящих в эту клику. Доказательство. Рассмотрим двудольный граф 2 , одну долю которого составляет множество вершин, а вторую - множество клик графа Г и смежность соответствует включение вершины в клику. Так как Г д.т.г. и с2 = 1 , то Z, локально 2-транзитивный граф. Отсюда непосредственно следует утверждение леммы.Л

Примитивные представления неабелевых простых групп порядка меньше ТО6

В этом параграфе описывается способ построения дистанционно-транзитивных графов путем решения задачи транзитивного расширения групп подстановок.

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

Дадим более точные формулировки. Пусть задана группа подстановок (н,&) и для некоторой точки хеЛ , н(х) = н , в частности н интранзитивна. Задача транзитивного расширения формулируется следующим образом. Требуется построить все такие транзитивные группы подстановок (G,fl) , что G(x) = н(х) = н .

Классическим является случай, когда н действует транзитивно на Л\ {х} , в этом случае (G,D. ) дважды транзитивна. Необходимые и достаточные условия существования транзитивного расширения в этом случае были найдены Дж. Холиоке [95] . Однако проверка этих условий весьма затруднительна. Известе н ряд комбинаторных подходов к решению задачи транзитивного расширения. При этом, как правило, расширения группы н связываются с расширением определенных структур, инвариантных относительно н ( блок-схемы, проективные плоскости и т.д.) . Обзор таких подходов содержится в [l2] (см. также [23]).

Поскольку мы интересуемся определенными графами, инвариантными относительно искомой группы (G,i) , то, с целью исключения тривиальных случаев полных и пустых графов, будем ограничиваться случаем интранзитивного действия н на Л \ { зс} Итак, теперь уместно сузить формулировку интересующей нас в дальнейшем задачи, которую будем называть стандартной задачей транзитивного расширения интранзитивной группы подстановок.

Пусть задана группа подстановок (н,1), н(х) = н и н действует интранзитивно на множестве Ц \ {х} . Требуется построить все транзитивные расширения (б,л ) группы (н,Л ) при следующих дополнительных условиях: (і) группа (G,xz) является 2-замкнутой; (ii) заданы структурные константы V-кольца группы (G,.).

В случае построения д.т.г. Г с заданным массивом пересечений пункт (і) означает, что в качестве н следует рассматривать полный фиксатор вершины в группе Aut( Г ) , а пункт (ii) обеспечивает построения графа именно для заданного массива пересечений.

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

Предлагаемый алгоритм решения стандартной задачи транзитивного расширения в общих чертах сводится к следующему: A - строится V-кольцо интранзитивной группы подстановок (Н,П); в - перечисляются все клеточные подкольца в построенном V-кольце, имеющие заданные структурные константы; с - проверяется комбинаторная регулярность построенных подко лец; D - для каждого отсеяного подкольца строится фиксатор н(у) = н(х,у) концов ребра некоторого связного неориентированного графа подкольца; Е - находится нормализатор группы Н(у) в симметрической группе множества П. , а в этом нормализаторе ищутся все подгруппы, содержащие Н(у) в качестве подгруппы индекса 2; F - фиксируется некоторая подстановка из каждой найденной подгруппы и проверяется, является ли она автоморфизмом рассматриваемого подкольца. Результатом действия алгоритма являются пары (подкольцо, подстановка ) , каждая из которых соответствует решению стандартной задачи.

На идейном уровне предложенный: алгоритм изложен в [24] . Общая схема этапов А, в, с была анонсирована в [l4j и применена к построению а.г. степени 10 на 65 вершинах, вопрос о существовании которого был поставлен Н.Биггсом (см. 4.1) . При этом искомая подстановка была найдена с помощью программы нахождения полной группы автоморфизмов графа. Заметим, что отдельные фрагменты алгоритма в случае групп ранга 3 неявно присутствуют в работе [137].

Значительное сокращение перебора при реализации шагов А - р позволяет получить предложенный автором метод неподвижных точек. При решении задачи транзитивного расширения этот метод состоит в следующем. Рассматривается некоторая подгруппа Р Н и множество ее неподвижных точек А (Р) при действии на П . Так как искомая группа G действует транзитивно на л , мы можем воспользоваться леммой. 3.3.6 ж установить возможную структуру орбит N„(P) на множестве Д (Р) .В частности, если р сопряжена в н со всеми- такими подгруппами Р» , что р» = р , то NQ(F) транзити-вен на Д(Р) . В атом случае приходим к задаче транзитивного расширения (NH(P), А(Р)) .