Содержание к диссертации
Введение
Вполне регулярные графы и блок-схемы 18
Автоморфизмы дистанционно регулярного графа с массивом пе ресечений {60,45, 8,1,12, 50} 37
Графы Крейна без треугольников 57
Список литературы 72
- Вполне регулярные графы и блок-схемы
- Автоморфизмы дистанционно регулярного графа с массивом пе ресечений {60,45, 8,1,12, 50}
- Графы Крейна без треугольников
Введение к работе
В комбинаторном анализе проблемой общего характера является задача размещения элементов в заданном числе множеств таким образом, чтобы г-ый элемент появлялся г І раз во всей совокупности этих множеств, чтобы j-oe множество содержало точно kj элементов и, наконец, чтобы пары, тройки и тому подобные наборы элементов появлялись определенное число раз. Такое размещение может быть названо системой инцидентности. В частности, в прикладной математике (статистика, теория планирования экспериментов) чаще используется понятие уравновешенной неполной блок-схемы, в которой всякий набор элементов (блок) состоит точно из к элементов (точек), каждая точка принадлежит точно г блокам, и каждая пара различных точек появляется вместе точно в Л блоках [8].
Блок-схема является частным случаем t-схем (с параметрами (v,k,X)), которые определяются как пара (X, В), где X — множество точек, В — множество блоков, каждый из которых содержит точно к точек, и любые t точек принадлежат вместе точно Л блокам. Таким образом, блок-схема является 2-схемой с подходящими параметрами.
Взаимосвязь блок-схем с другими объектами комбинаторного анализа — кодами, исправляющими ошибки, графами, хорошо известна и исследовалась ранее (см. [19]).
Далее мы рассматриваем неориентированные графы без петель и кратных ребер. В таком случае граф можно определить как пару, состоящую из множества вершин и множества ребер, то есть неупорядоченных двухэлементных подмножеств множества вершин. Заметим, что любой регулярный граф (то есть граф, в котором каждая вершина смежна с одним и тем же числом вершин) является 1-схемой, а полный граф (клика) является 2-схемой (схемой нар или полной схемой).
Использование более сильных условий регулярности для графа позволяет ввести понятие сильно регулярного графа с параметрами (v, к, А, //), который определяется как граф на v вершинах, регулярный степени к, в котором пересечение окрестностей любой пары различных вершин содержит точно Л или ц вершин в зависимости от того, смежны эти вершины или нет. Впервые понятие сильно регулярного графа было введено Боузом [12] при изучении частичных геометрий и уравновешенных неполных блок-схем. Так, например, хорошо известно [12], что блок-граф 2 — (v,k,l) схемы, в котором два блока смежны тогда и только тогда, когда они имеют непустое пересечение, является сильно регулярным графом. Этот факт был обобщен Боузом, Геталсом и Зейделем для блок-графов квазисимметричных схем [19]. Таким образом, блок-схемы позволяют получить примеры сильно регулярных графов. Однако изучение этих графов не дает дополнительной информации о схемах. Напротив, изучение схем, возникающих в сильно регулярных графах, позволяет в ряде случаев установить некоторые структурные особенности графа, в том числе, доказать его несуществование.
Вместе с тем, к понятию сильно регулярного графа можно прийти и другим путем, рассматривая действие некоторой группы перестановок G на конечном множестве V. Будем говорить, что G имеет подстановочный ранг 3, если G транзитивно действует на V и имеет точно 3 орбиты на V х V: диагональ {(р,р) P V} и еще-две"другие орбиты 0 0 -. Если группа ранга 3-имест четный порядок, то она содержит инволюцию, переставляющую, скажем, точки р и q. Таким образом, орбита, содержащая р и q, симметрична. Образуем граф Г, вершинами которого являются элементы V, а ребрами — неупорядоченные пары, соответствующие упорядоченным парам из О. Тогда группа G вкладывается в группу автоморфизмов графа Г, а граф Г является сильно регулярным. Теория групп ранга 3 была развита в работах Д. Хигмана ([24]-[30]).
В дальнейшем, для вершины а графа Г через Т{(а) будем обозначать подграф, индуцированный на множестве вершин, находящихся в Г на расстоянии г от вершины а. Для вершин a, b Є Г через d(a, b) будем обозначать расстояние между а и 6 в Г. Кроме того, всюду далее под подграфом будем понимать только индуцированный подграф. Подграф Гі(а) называется окрестностью вершины а и обозначается через [а]. Через aL обозначается подграф, являющийся шаром радиуса 1 с центром а. В соответствии с приведенным выше определением, граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Очевидно, что графами, построенными по группам ранга 3, теория сильно регулярных графов не исчерпывается. Дальнейшим обобщением таких графов являются дистанционно транзитивные графы диаметра d = d(T), группы автоморфизмов которых действуют транзитивно на множествах {(и, w) \ и, w Є r,dr(u,w) = і} для любого і Є {0,...,d}. Комбинаторным обобщением сильно регулярных графов являются дистанционно регулярные графы, для которых существуют такие натуральные числа pf-, i,j, к Є {0,..., d} что Гг-(і4) ПГДги)! = р\- для любых вершин и, w, находящихся па расстоянии к в Г (см. [13]).
Отметим, в частности, что изучение дистанционно транзитивных графов связано с поиском единого представления конечных простых групп — задачей, которая стала актуальной после "завершения" классификации конечных простых групп ([13]-[17], [34], [36], [39]).
Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах прошлого века. Пусть L(Kn) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п) (или, что тоже самое, блок-граф полной 2-схемы). Этот граф является сильно регулярным графом с параметрами (Q) 2(п — 2), п — 2,4J. В работах 1959-60 годов Л. Чанг [21] и А. Хоффман ([31], [32]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех га, за исключением га = 8. Для случая га = 8 было показано, что, кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [20].
Реберный граф Ь(Кт,п) полного двудольного графа Кт п с долями порядков тип является кореберно регулярным графом (см. [13]) с параметрами (mra, m-fra—2, 2). Граф L(Km:Jl) называют тхп решеткой. При т = га эта решетка является сильно регулярным графом с параметрами (га2, 2га—2, п—2, 2). С. Шрикханде в [38] показал, что граф, имеющий параметры га х га решетки является решеткой при п/ 4. При га = 4 существует еще один сильно регулярный граф с параметрами решетки, но не изомофрный ей, названный графом Шрикханде.
Дж. Зейдель [37] показал, что кроме треугольных графов Т(га) и га х га-решетки, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Петсрсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
Одной из нерешенных проблем в теории комбинаторно симметричных графов остается задача о существовании графа с заданным условиями комбинаторной симметрии, например, существование сильно регулярного графа с заданными параметрами. Если эту задачу решить для конкретного графа не удается, может оказаться "полезной-информация "о свойствах группы авто- морфизмов (например, информация о простых делителях порядка группы и подграфах неподвижных точек автоморфизмов простого порядка) этого гипотетического графа, в частности, при попытке построения графа с помощью компьютера. Для дистанционно регулярных графов оказывается возможным получение такой информации с помощью теории характеров конечных групп [18]. Кроме того, эта информация может быть существенно уточнена, если известно, что гипотетический граф связан с некоторой схемой.
Введем еще несколько определений и обозначений. Граф Г называется вполне регулярным графом с параметрами (v,k,\, fz), если Г содержит v вершин, регулярен степени к, каждое ребро из Г лежит точно в Л треугольниках, и подграф [а] П [Ь] содержит точно /л вершин для любой пары вершин а, 6, находящихся на расстоянии 2 в Г. Очевидно, что вполне регулярный граф диаметра 2 является сильно регулярным графом.
Подграф [а] Г) [Ь] будем называть Х-подграфом, если d(a,b) = 1. Если же d(a, 6) = 2, то соответствующий подграф назовем ц-подграфом.
Если вершины и, w находятся на расстоянии г в Г, то через b{(u,w) (соответственно Сг(гб,ги)) обозначим число вершин в пересечении Г(ад) с Гі+\(и) (соответственно ГІ_І(П)). Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {&о • • • &d-i5 съ • • • 5 cd}, если значения b{ = bi(u,w) и сі — Ci(u,w) не зависят от выбора вершин и, w на расстоянии г в Г для любого г — 0,...,(1 Можно показать, что это определение дистанционно регулярного графа равносильно приведенному выше (см. [13]).
Цель диссертации. Целью данной работы является решение следующих задач.
1) Изучить вполне регулярные графы Г диаметра d 3, в которых для некоторой вершины а Є Г пара (Г (а), Г -і(а)) является 2-схемой относительно отношения инцидентности, индуцированного смежностью в графе.
2) Изучить возможные автоморфизмы гипотетических дистанционно регулярных графов с массивом пересечений {60,45, 8; 1,12, 50}.
3) Изучить вопрос о существовании сильно регулярных графов с параметрами ((г2 + Зг)2,г3 + Зг2 + г, 0, г2 + г) при г 3, изучить возможные автоморфизмы графов из этой серии.
Методы исследования. Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них ел едущие.
1. Исследованы вполне регулярные графы Г диаметра d 3, в которых для некоторой вершины обГ пара (Г (а), Г /_і(а)) является 2-схемой относительно отношения инцидентности, индуцированного смежностью в графе. Определены возможные параметры графов при d = 3 в случаях, когда Гз(а) является графом Зейделя или когда указанная 2-схема является симметричной.
2. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов простых порядков дистанционно регулярных графов с массивом пересечений {60,45,8; 1,12, 50}.
3. Доказано несуществование сильно регулярного графа с параметрами ((r2 + 3r)2,r3 + 3r2 + r, 0,r2 + r) при г = 3 и, как следствие, нерасширяемость симметричной 2 — (56,11,2) схемы до 3-схемы.
4. Найдены возможные простые делители порядка группы автоморфизмов сильно регулярных графов с параметрами ((г2 -f- Зг)2, г3 + Зг2 + г, 0, г2 + г) при г = 4. Доказано, что группа автоморфизмов такого графа не квазипри-митивна.
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение комбинаторно симметричных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Апробация работы. Основные результаты диссертации докладывались на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения А.И.Старостина (Нальчик, 2006 г.) и 35-й, 36-ой и 37-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2004-2006 гг.).
Результаты работы неоднократно докладывались и обсуждались на алгеб раическом семинаре ИММ УрО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [40]—[48]. Работы [40]—[47] выполнены в нераздельном соавторстве с А.А. Мах-певым.
Структура и объем работы. Диссертация состоит из введения, трех глав и списка цитированной литературы, содержащего 48 наименований.
Результаты диссертации.
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты.
В первой главе рассматриваются вполне регулярные графы Г диаметра d, в которых для некоторой вершины а Є Г пара (Г (а), Гс/_і(а)) является 2-схемой (блок-схемой) относительно отношения инцидентности, индуцированного смежностью в графе.
Блок-схемы естественно возникают внутри сильно регулярных графов. Например, если для клики или коклики X графа Г достигается равенство в границе Хоффмана (см. [13]), то пара (X, Г — X) является 2-схемой. В монографии Камерона и ван Линта [14, § 8] рассматривается случай, когда в сильно регулярном графе Г для некоторой вершины а пара (Г(а), Г2(а)) является 2-схемой, в которой точка и блок инцидентны, только если они смежны в Р. Например, если Г — полный многодольный_граф_.Кпхт, то для любой вершины а пара (Г(а),Г2(а)) является вырожденной 2-схемой, имеющей точно т — 1 блок, причем каждый блок инцидентен всем точкам. Второй класс примеров дают сильно регулярные графы без треугольников.
Следующие результаты являются основными в главе I.
Предложение 1. Пусть Г — связный вполне регулярный граф диаметра d с параметрами (у,к,\,ц), в котором для некоторой вершины а пара (Г(і(а),Г _і(а)) является 2-(У, В, R, К, Л) схемой. Тогда R = Cd(a,x) для х Є Td{a), К = 6rf-i(a, у) для у Є Г -і(а) и подграф Г(і(а) является кли кой, кокликой или сильно регулярним графом с параметрами [у = У, k = k-R,\ = \-A}ii = fi-A).
Класс дистанционно регулярных графов Г, в которых для некоторой вершины а подграф Г (а) является кокликой, содержит антиподальные и дву-дольные графы, для этих графов Л равно 0 (и 2-схема вырождена) и /І соответственно.
Пример 1. Следующие дистанционно регулярные графы диаметра d 3 являются двудольными, но не антиподальными:
(1) обобщенные n-угольники порядка (1, q) для п = 6, 8,12;
(2) удвоения графов Грассмана;
(3) графы типов (В0-В7) и типа (В 14) [9, таблица 6.9].
Графы типа (ВО) — это графы инцидентности симметричных 2-схем, графы типа (В1) возникают из кодов Казами, графы типов (В2-В7) — это графы инцидентности частичных //-геометрий (см. [9, §1.7]).
Дистанционно регулярный граф Г, в котором для некоторой вершины а подграф Г (а) — клика, оказывается половинным графом дистанционно регулярного графа нечетного диаметра 2d + 1, являющегося антиподальным 2-накрытием.
Пример 2. Следующие дистанционно регулярные графы диаметра 2d + - 1- 7 являются-двудольными и антиподальными-2-накрытиями: — —
(1) удвоения нечетных графов на 2d +1 точках (половинные графы являются графами Джонсона J(2d + 1, d));
(2) (2d + 1)-куб;
(3) графы диаметра 7 на 2048 вершинах (удвоение графа смежных классов усеченного бинарного кода Голея) и на 4096 вершинах (удвоение графа смежных классов бинарного кода Голея).
Примеры сильно регулярных графов Г, в которых для некоторой вершины а пара (Гг(а), [а]) является 2-схемой, приведены в [19]. Пример дистанционно регулярного графа Г диаметра, большего 2, в котором для некоторой вершины а подграф Г (а) является сильно регулярным графом, обеспечивает граф Джонсона J (2d + 2,d). Для этого графа получим Л = 2d,/i = 4, для любой вершины а имеем Г (а) = T(d+2) — сильно регулярный граф с Л = d, // = 4. Но для этого графа не выполняется равенство Л — Л = // — //.
Теорема 1. Пусть Г — вполне регулярный граф диаметра З, имеюіций параметры (v, &, А, /л). Тогда следующее утвероісдения равносильны:
(1) Г является дистанционно регулярным графом, в котором для каждой вершины а подграф Гз(а) является кликой, кокликой или сильно регулярным графом с параметрами (г/, А; , Л , ц ), где X — X = ц — /і ;
(2) для любой вершины а пара (Гз(а),Г2(а)) является 2-схемой.
Автору не известны примеры дистанционно регулярных графов диаметра d 3 с параметрами (v, к, А, ц), в которых для некоторой вершины а подграф; Гс/(а) был бы сильно регулярным диаметра 2 с параметрами (?/, к , А , ц ) и Л - Л = /х - /і .
Для некоторых сильно регулярных графов Е найдены возможные параметры вполне регулярных графов Г диаметра 3, в которых найдется такая вершина а, что Гз(а) = Е и пара (Гз(а), Г2(а)) является 2-схемой.
Теорема 2. Пусть Е — сильно регулярный граф, Г — вполне регулярный граф-диаметра 3, имеющий-параметры-(и, к, A, fi) и вершину а такую, -что Гз(а) = Т и пара (Гз(а),Г2(а)) является 2-схемой. Тогда выполняются следующие утверждения:
(1) если схема (Е,Г2(а)) симметрична, то Г — семиугольник;
(2) если Е является п X п решеткой, то схема (Е,Г2(а)) имеет параметры (п2,4п2, 2(гг+1), (n +1)/2,1), п нечетно, и граф Г имеет параметры (Ъп2 + 4п + 1,4п, п - 1,3);
если Е — полный многодольный граф КГХ2, граф Мура, Клебша, Шрик-ханде, Шлефли, один из графов Чанга, п X п решетка при п 50; или тре угольный граф Т(п) при п 50, то. полный список допустимых параметров графов, не вошедших в указанную в (2) бесконечную серию, содероюится в таблице 1.
Таблица 1.
N граф точек схемы параметры схемы параметры графа
1 граф Петерсена (10,30,12,4,4) (56,15,4,5)
2 граф Хофмана-Синглтона (50,1050,168,8,24) (1276,175,24,25)
3 граф Шрикханде (16,360,90,4,18) (473,96,20,20)
4 решетка на 9 вершинах (9,24,8,3,2) (46,12,3,4)
5 решетка на 16 вершинах (16,360,90,4,18) (473,96,20,20)
6 решетка на 36 вершинах (36,225,50,8,10) (322,60,14,12)
7 решетка на 100 вершинах (100,825,132,16,20) (1076,150,28,22)
8 решетка на 441 вершинах (441,2940,80,12,2) (3502,120,21,4)
9 Т(9) (36,84,14,6,2) (149,28,9,6)
10 Т(11) (55,264,48,10,8) (386,66,17,12)
11 Т(14) (91,195,15,7,1) (336,39,13,5)
12 Т(14) (91,546,60,10,6) (722,84,18,10)
13 Т(15) (105,910,104,12,11) (1146,130,24,15)
14 Т(15) (105,520,104,21,20) (756,130,33,24)
15 Т(17) (136,8568,378,6,14) (9113,408,29,18)
16 Т(20) (190,513,135,50,35) (875,171,53,39)
17 Т(25) (300,4600,414,27,36) (5361,460,59,40)
18 Т(35) (595,22440,1056,28,48) (24158,1122,81,52)
" "Для дистанционно-регулярных-графов диаметра d- -3-f в которых для -любой вершины а пара (Та(а),Т(і-і(а)) является 2-схемой, результаты первой главы диссертации позволяют выдвинуть следующее предположение.
Гипотеза. Если Г — дистанционно регулярный граф диаметра d 3, в котором для любой вершины а пара (I\j(a),rV_i(a)) является 2-схемой, то подграф Е = ГДа) является кликой или кокликой.
Указанная гипотеза подтверждается тем, что среди допустимых массивов пересечений дистанционно регулярных графов, приведенных в [13], лишь два массива {60,45, 8; 1,12, 50} и {49,36,8; 1, 6,42} отвечают графам, для которых могут быть выполнены условия нашей гипотезы.
Для первого массива Гз(а) является 6x6 решеткой, а для второго — объединением семи изолированных 8-клик. Однако, в лемме 1.4.4 первой главы диссертации доказано, что в дистанционно регулярном графе с массивом пересечений {60,45, 8; 1,12, 50} найдется вершина, третья окрестность которой не является 6x6 решеткой. Для второго массива пара (Гз(а), Г2(а)) является (V,B,R,K,A)-cxeMO&, где V = 56, В = 294, R = 42, К = 8 и Л = R(K — 1)/ (V — 1) = 42 • 7/55 (дробность числа Л показывает наличие вершин в Гз(а), находящихся на расстоянии 3, что противоречит предположению, что пара (Гз(а),Г2(а)) является 2-схемой в указанном смысле). Таким образом, не известны массивы пересечений, которым бы отвечали дистанционно регулярные графы, третья окрестность каждой вершины которых является сильно регулярным графом, а пара (Г (а), Г _і(а)) является 2-схемой.
Во второй главе изучаются автоморфизмы гипотетического дистанционно регулярного графа с массивом пересечений {60,45,8; 1,12, 50}. Этот граф имеет спектр {601,1445, О207, —1069}, является Q-полиномиальным, граф Г2 (в котором вершины смежны тогда и только тогда, когда они находятся на расстоянии 2 в Г) сильно регулярен с параметрами (322, 225,160,150) и является псевдогеометрическим для частичной геометрии pG2(6,15).
Введем следующее обозначением Пусть-Т —граф} тогда-для-элемента д-группы G = Aut(r) через Fix(g) обозначим подграф вершин графа Г, фиксируемых автоморфизмом д.
Следующие теорема и следствие являются основными во второй главе.
Теорема 3. Пусть Г — дистанционно регулярный граф, имеющей массив пересечений {60,45,8; 1,12, 50}, G = Aut(r), g — элемент из G простого порядка р Ъ и Q = Fix(g). Тогда верно одно из утверждений:
(1) р = 7 или 23 и Г2 — пустой граф;
(2) p = 5 и либо
(і) Г2 состоит из двух вершин, находящихся на расстоянии 3 в Г, либо (И) \Q\ = 7 и Гз(а) П Сі является 6-кликой для некоторой вершины абП.
Следствие 1. Дистанционно регулярный граф с массивом пересечений {60,45,8; 1,12, 50} не являет,ся дистанционно транзитивным.
Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г. Хигмен предложил оригинальный метод, использующий теорию характеров конечных групп. Этот метод изложен в монографии П. Камерона "Группы подстановок", причем ранее он применялся только к изучению инволютивных автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1). Позднее, в работах [1]-[3] изучались автоморфизмы сильно регулярных графов с малыми числами пересечений. В диссертации этот метод применяется для изучения автоморфизмов гипотетического дистанционно регулярного графа с массивом пересечений {60,45,8; 1,12, 50}.
В третьей главе доказывается несуществование сильно регулярного графа с параметрами ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) для г = 3 и изучаются автоморфизмы графов из этой серии для г — 4.
Введем далее некоторые определения. Полный п-дольный граф с долями порядков mi,...,ran обозначим через Кти_}ГПп. Граф К\ т называется т-лапой. Граф -К"і,...,і,з с п долями порядка 1 называется п-короной (короной, если п = 2). Кликовым расширением графа Г называется граф, полученный заменой каждой вершины а на клику (а), причем различные клики попарно не пересекаются, и вершина из (а) смежна со всеми вершинами из (6) тогда и только тогда, когда а, Ь смежны в Г. Граф Г называется редуцированным, если для любой вершины а Є Г множество {х Є Г XА- = а1} состоит только из вершины а.
Хороню известно, что на строение графа сильное влияние оказывают его /л-подграфы. Так, например, в работе [35] М. Нумата получил классификацию графов без корон, в которых /х-подграфы являются изоморфными реберно регулярными графами диаметра 2 (естественно, не имеющими 3-лап).
В работе [7] исследовались связные редуцированные регулярные графы без корон, в которых каждый -подграф реберно регулярен с заданными параметрами (г/, к , А ), к 0.
По следствию 2 теоремы 2 из [7] связный редуцированный регулярный граф Г без корон, в котором каждый /і-подграф реберно регулярен с заданными параметрами (г/, & , А ), к 0 и имеет диаметр не более 2, является одним из следующих графов:
(1) Г не содержит 3-коклик и либо является октаэдром или треугольным графом Т(5), либо граф Г сильно регулярен и имеет параметры ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) для некоторого г 1, либо нетривиальным клико-вым расширением пятиугольника;
(2) Г содержит 3-коклику, не содержит 3-лап и является кликовым расширением графа икосаэдра, треугольным графом Т(т) при га 6 или графом Шлефли;
(3) Г содержит 3-лапу и является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета.
Напомним [19], что сильно регулярный граф Г с параметрами (г , /г, А,д) имеет точно 3 различных собственных значения k,r:s. Если графы Г и Г связны, то выполняются неравенства, называемые условиями Крейна:
(1) (r + l)(fc + r + 2rs) (fc + r)(s+l)2 и
(2) (s + l)(k + s + 2rs) {k + s)(r + 1)2.
Граф Г назовем графом Крейна, если для него достигается равенство в одном из условий Крейна (1) или (2). По теореме 8.15 из [19] для любой вершины а графа Крейна Г подграфы [а] и Г2(а) сильно регулярны. Пусть Г является графом Крейна без треугольников. Ввиду предложения 8.12 и теорем 8.7 и 8.8 из [19] сильно регулярный граф Г без треугольников с 2 /і к имеет параметры ((г2 + Зг)2,г3 + Зг2 + г, 0, г2 4- г) тогда и только тогда, когда любая 3-коклика из Г попадает в окрестность ровно г вершин. Такой граф обозначим через Кге(г). Далее, для любых смежных вершин а, Ъ Є Г подграфы Г2(а) и Г2(а) П Г2(6) сильно регулярны с параметрами ((r2 + 2r - l)(r2 + 3r + l),r3 + 2r2,0,r2) и ((г2 + 2r)(r2 + 2г - 1),г3 + г2 -г, 0, г2 - г) соответственно. Известно, что в случаях г = 1 и 2 существуют единственные графы Кге(г) — граф дополнительный к графу Клебша и граф Хигмена-Симса соответственно. Последний граф построен в 1968 г. вместе со спорадической простой группой Хигмена-Симса.
Существование графов Кге(г) при г 3 в общем случае остается неизвестным. В соответствии с этим в работе [7] была поставлена
Проблема 1. Существует ли сильно регулярный граф с параметрами ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) в случае г 3?
Отметим, что вопрос о существовании графа Кге(3) непосредственно связан с еще одной известной проблемой из теории схем. Пусть Г = Кге(г). Рассмотрим схему V = ([а], Г2(а)), где точка Ь Є [а] инцидентна блоку В Є Г2(а) тогда и только тогда, когда b и В смежны в Г. Тогда 3-схема Т является расширением симметричной 2-схемы V = ([а] — {6}, [Ь] — {а}). Проблема существовани расширений схем является одной из нерешенных и наиболее важных задач в теории схем (см. [19]).
В частности, если г = 3, то схема ТУ является 2 — (56,11, 2) схемой. Но вопрос о существовании расширения схемы 2 — (56,11,2) более 30 лет оставался открытым. Ранее, Багчи, изучая самоортогональный код над i7 , отвечающий строкам матрицы инцидентности гипотетической 3-(57,12,2) схемы, доказал несуществование таких 3-схем (см. [10]). Однако в его работе была допущена ошибка (см. [14]). В теореме 1 из работы [5] утверждалось, что граф Кге(г) не содержит Кг г подграфов, в частности, граф Кге(3) не существует. Однако в лемме 3 из [5] была допущена арифметическая ошибка.
Один из основных результатов третьей главы диссертации заключается в следующих теореме и следствии из неё.
Теорема 4. Не существуют сильно регулярные графы с параметрами ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) для г = 3.
Следствие 2. Симметричные 2-(56,11,2) схемы нерасширяемы.
В заключение третьей главы изучается группа автоморфизмов гипотетического сильно регулярного графа Кге(4).
Отметим, что для изучения возможных порядков и подграфов неподвижных точек автоморфизмов графа Кге(4) используется метод Хигмеиа. Автоморфизмы графа Кге(5) изучались в [1].
Пусть G — транзитивная группа подстановок на множестве X. Группа G называется квазипримитивной на X, если любая неединичная нормальная подгруппа из G действует транзитивно на X.
Теорема 5. Пусть Г — граф Крейна Kre{4), G = Aut(r). Если g — элемент простого порядка р из G, 7 = Fix(g), то р Є {2,7}, причем в случае р = 7 автоморфизм g действует без неподвижных точек.
Следствие 3. Действие группы G на вершинах графа Г не квазиприми-тивпо.
Вполне регулярные графы и блок-схемы
В комбинаторном анализе проблемой общего характера является задача размещения элементов в заданном числе множеств таким образом, чтобы г-ый элемент появлялся г І раз во всей совокупности этих множеств, чтобы j-oe множество содержало точно kj элементов и, наконец, чтобы пары, тройки и тому подобные наборы элементов появлялись определенное число раз. Такое размещение может быть названо системой инцидентности. В частности, в прикладной математике (статистика, теория планирования экспериментов) чаще используется понятие уравновешенной неполной блок-схемы, в которой всякий набор элементов (блок) состоит точно из к элементов (точек), каждая точка принадлежит точно г блокам, и каждая пара различных точек появляется вместе точно в Л блоках [8].
Блок-схема является частным случаем t-схем (с параметрами (v,k,X)), которые определяются как пара (X, В), где X — множество точек, В — множество блоков, каждый из которых содержит точно к точек, и любые t точек принадлежат вместе точно Л блокам. Таким образом, блок-схема является 2-схемой с подходящими параметрами.
Взаимосвязь блок-схем с другими объектами комбинаторного анализа — кодами, исправляющими ошибки, графами, хорошо известна и исследовалась ранее (см. [19]). Далее мы рассматриваем неориентированные графы без петель и кратных ребер. В таком случае граф можно определить как пару, состоящую из множества вершин и множества ребер, то есть неупорядоченных двухэлементных подмножеств множества вершин. Заметим, что любой регулярный граф (то есть граф, в котором каждая вершина смежна с одним и тем же числом вершин) является 1-схемой, а полный граф (клика) является 2-схемой (схемой нар или полной схемой). Использование более сильных условий регулярности для графа позволяет ввести понятие сильно регулярного графа с параметрами (v, к, А, //), который определяется как граф на v вершинах, регулярный степени к, в котором пересечение окрестностей любой пары различных вершин содержит точно Л или ц вершин в зависимости от того, смежны эти вершины или нет. Впервые понятие сильно регулярного графа было введено Боузом [12] при изучении частичных геометрий и уравновешенных неполных блок-схем. Так, например, хорошо известно [12], что блок-граф 2 — (v,k,l) схемы, в котором два блока смежны тогда и только тогда, когда они имеют непустое пересечение, является сильно регулярным графом. Этот факт был обобщен Боузом, Геталсом и Зейделем для блок-графов квазисимметричных схем [19]. Таким образом, блок-схемы позволяют получить примеры сильно регулярных графов. Однако изучение этих графов не дает дополнительной информации о схемах. Напротив, изучение схем, возникающих в сильно регулярных графах, позволяет в ряде случаев установить некоторые структурные особенности графа, в том числе, доказать его несуществование.
Вместе с тем, к понятию сильно регулярного графа можно прийти и другим путем, рассматривая действие некоторой группы перестановок G на конечном множестве V. Будем говорить, что G имеет подстановочный ранг 3, если G транзитивно действует на V и имеет точно 3 орбиты на V х V: диагональ {(р,р) P V} и еще-две"другие орбиты 0 0 -. Если группа ранга 3-имест четный порядок, то она содержит инволюцию, переставляющую, скажем, точки р и q. Таким образом, орбита, содержащая р и q, симметрична. Образуем граф Г, вершинами которого являются элементы V, а ребрами — неупорядоченные пары, соответствующие упорядоченным парам из О. Тогда группа G вкладывается в группу автоморфизмов графа Г, а граф Г является сильно регулярным. Теория групп ранга 3 была развита в работах Д. Хигмана ([24]-[30]). В дальнейшем, для вершины а графа Г через Т{(а) будем обозначать подграф, индуцированный на множестве вершин, находящихся в Г на расстоянии г от вершины а. Для вершин a, b Є Г через d(a, b) будем обозначать расстояние между а и 6 в Г. Кроме того, всюду далее под подграфом будем понимать только индуцированный подграф. Подграф Гі(а) называется окрестностью вершины а и обозначается через [а]. Через aL обозначается подграф, являющийся шаром радиуса 1 с центром а. В соответствии с приведенным выше определением, граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Автоморфизмы дистанционно регулярного графа с массивом пе ресечений {60,45, 8,1,12, 50}
Очевидно, что графами, построенными по группам ранга 3, теория сильно регулярных графов не исчерпывается. Дальнейшим обобщением таких графов являются дистанционно транзитивные графы диаметра d = d(T), группы автоморфизмов которых действуют транзитивно на множествах {(и, w) \ и, w Є r,dr(u,w) = і} для любого і Є {0,...,d}. Комбинаторным обобщением сильно регулярных графов являются дистанционно регулярные графы, для которых существуют такие натуральные числа pf-, i,j, к Є {0,..., d} что Гг-(і4) ПГДги)! = р\- для любых вершин и, w, находящихся па расстоянии к в Г (см. [13]).
Отметим, в частности, что изучение дистанционно транзитивных графов связано с поиском единого представления конечных простых групп — задачей, которая стала актуальной после "завершения" классификации конечных простых групп ([13]-[17], [34], [36], [39]).
Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах прошлого века. Пусть L(Kn) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п) (или, что тоже самое, блок-граф полной 2-схемы). Этот граф является сильно регулярным графом с параметрами (Q) 2(п — 2), п — 2,4J. В работах 1959-60 годов Л. Чанг [21] и А. Хоффман ([31], [32]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех га, за исключением га = 8. Для случая га = 8 было показано, что, кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [20].
Реберный граф Ь(Кт,п) полного двудольного графа Кт п с долями порядков тип является кореберно регулярным графом (см. [13]) с параметрами (mra, m-fra—2, 2). Граф L(Km:Jl) называют тхп решеткой. При т = га эта решетка является сильно регулярным графом с параметрами (га2, 2га—2, п—2, 2). С. Шрикханде в [38] показал, что граф, имеющий параметры га х га решетки является решеткой при п/ 4. При га = 4 существует еще один сильно регулярный граф с параметрами решетки, но не изомофрный ей, названный графом Шрикханде.
Дж. Зейдель [37] показал, что кроме треугольных графов Т(га) и га х га-решетки, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Петсрсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
Одной из нерешенных проблем в теории комбинаторно симметричных графов остается задача о существовании графа с заданным условиями комбинаторной симметрии, например, существование сильно регулярного графа с заданными параметрами. Если эту задачу решить для конкретного графа не удается, может оказаться "полезной-информация "о свойствах группы авто- морфизмов (например, информация о простых делителях порядка группы и подграфах неподвижных точек автоморфизмов простого порядка) этого гипотетического графа, в частности, при попытке построения графа с помощью компьютера. Для дистанционно регулярных графов оказывается возможным получение такой информации с помощью теории характеров конечных групп [18]. Кроме того, эта информация может быть существенно уточнена, если известно, что гипотетический граф связан с некоторой схемой. Введем еще несколько определений и обозначений. Граф Г называется вполне регулярным графом с параметрами (v,k,\, fz), если Г содержит v вершин, регулярен степени к, каждое ребро из Г лежит точно в Л треугольниках, и подграф [а] П [Ь] содержит точно /л вершин для любой пары вершин а, 6, находящихся на расстоянии 2 в Г. Очевидно, что вполне регулярный граф диаметра 2 является сильно регулярным графом.
Подграф [а] Г) [Ь] будем называть Х-подграфом, если d(a,b) = 1. Если же d(a, 6) = 2, то соответствующий подграф назовем ц-подграфом. Если вершины и, w находятся на расстоянии г в Г, то через b{(u,w) (соответственно Сг(гб,ги)) обозначим число вершин в пересечении Г(ад) с Гі+\(и) (соответственно ГІ_І(П)). Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {&о&d-i5 съ 5 cd}, если значения b{ = bi(u,w) и сі — Ci(u,w) не зависят от выбора вершин и, w на расстоянии г в Г для любого г — 0,...,(1 Можно показать, что это определение дистанционно регулярного графа равносильно приведенному выше (см. [13]).
Графы Крейна без треугольников
Для первого массива Гз(а) является 6x6 решеткой, а для второго — объединением семи изолированных 8-клик. Однако, в лемме 1.4.4 первой главы диссертации доказано, что в дистанционно регулярном графе с массивом пересечений {60,45, 8; 1,12, 50} найдется вершина, третья окрестность которой не является 6x6 решеткой. Для второго массива пара (Гз(а), Г2(а)) является (V,B,R,K,A)-cxeMO&, где V = 56, В = 294, R = 42, К = 8 и Л = R(K — 1)/ (V — 1) = 42 7/55 (дробность числа Л показывает наличие вершин в Гз(а), находящихся на расстоянии 3, что противоречит предположению, что пара (Гз(а),Г2(а)) является 2-схемой в указанном смысле). Таким образом, не известны массивы пересечений, которым бы отвечали дистанционно регулярные графы, третья окрестность каждой вершины которых является сильно регулярным графом, а пара (Г (а), Г _і(а)) является 2-схемой. Во второй главе изучаются автоморфизмы гипотетического дистанционно регулярного графа с массивом пересечений {60,45,8; 1,12, 50}. Этот граф имеет спектр {601,1445, О207, —1069}, является Q-полиномиальным, граф Г2 (в котором вершины смежны тогда и только тогда, когда они находятся на расстоянии 2 в Г) сильно регулярен с параметрами (322, 225,160,150) и является псевдогеометрическим для частичной геометрии pG2(6,15). Введем следующее обозначением Пусть-Т —граф} тогда-для-элемента д-группы G = Aut(r) через Fix(g) обозначим подграф вершин графа Г, фиксируемых автоморфизмом д. Следующие теорема и следствие являются основными во второй главе. Теорема 3. Пусть Г — дистанционно регулярный граф, имеющей массив пересечений {60,45,8; 1,12, 50}, G = Aut(r), g — элемент из G простого порядка р Ъ и Q = Fix(g). Тогда верно одно из утверждений: (1) р = 7 или 23 и Г2 — пустой граф; (2) p = 5 и либо (і) Г2 состоит из двух вершин, находящихся на расстоянии 3 в Г, либо (И) \Q\ = 7 и Гз(а) П Сі является 6-кликой для некоторой вершины абП. Следствие 1. Дистанционно регулярный граф с массивом пересечений {60,45,8; 1,12, 50} не являет,ся дистанционно транзитивным.
Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г. Хигмен предложил оригинальный метод, использующий теорию характеров конечных групп. Этот метод изложен в монографии П. Камерона "Группы подстановок", причем ранее он применялся только к изучению инволютивных автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1). Позднее, в работах [1]-[3] изучались автоморфизмы сильно регулярных графов с малыми числами пересечений. В диссертации этот метод применяется для изучения автоморфизмов гипотетического дистанционно регулярного графа с массивом пересечений {60,45,8; 1,12, 50}.
В третьей главе доказывается несуществование сильно регулярного графа с параметрами ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) для г = 3 и изучаются автоморфизмы графов из этой серии для г — 4. Введем далее некоторые определения. Полный п-дольный граф с долями порядков mi,...,ran обозначим через Кти_}ГПп. Граф К\ т называется т-лапой. Граф -К"і,...,і,з с п долями порядка 1 называется п-короной (короной, если п = 2). Кликовым расширением графа Г называется граф, полученный заменой каждой вершины а на клику (а), причем различные клики попарно не пересекаются, и вершина из (а) смежна со всеми вершинами из (6) тогда и только тогда, когда а, Ь смежны в Г. Граф Г называется редуцированным, если для любой вершины а Є Г множество {х Є Г XА- = а1} состоит только из вершины а. Хороню известно, что на строение графа сильное влияние оказывают его /л-подграфы. Так, например, в работе [35] М. Нумата получил классификацию графов без корон, в которых /х-подграфы являются изоморфными реберно регулярными графами диаметра 2 (естественно, не имеющими 3-лап).
В работе [7] исследовались связные редуцированные регулярные графы без корон, в которых каждый -подграф реберно регулярен с заданными параметрами (г/, к , А ), к 0. По следствию 2 теоремы 2 из [7] связный редуцированный регулярный граф Г без корон, в котором каждый /і-подграф реберно регулярен с заданными параметрами (г/, & , А ), к 0 и имеет диаметр не более 2, является одним из следующих графов: (1) Г не содержит 3-коклик и либо является октаэдром или треугольным графом Т(5), либо граф Г сильно регулярен и имеет параметры ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) для некоторого г 1, либо нетривиальным клико-вым расширением пятиугольника; (2) Г содержит 3-коклику, не содержит 3-лап и является кликовым расширением графа икосаэдра, треугольным графом Т(т) при га 6 или графом Шлефли; (3) Г содержит 3-лапу и является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета.
