Содержание
Введение 3
1 Предварительные результаты 13
1.1 О хороших парах: вершин в реберно регулярных графах...........13
1.2 Некоторые свойства сильно регулярных графов...................24
і
»
2 О хороших парах вершин в реберно регулярных графах 28
2.1 Почти хорошие тройки в графах с к > З&і.......................28
2.2 Хорошие нары в графах с к > 36)................................35
2.3 Доказательство теоремы 2.......................................37
2.4 Реберно регулярный граф с к = 17,6і = 6.......................41
2.5 Хорошие пары в графах с к = ЗЬХ — 1...........................53
2.6 Графы без хороших мар..........................................61
3 О сильно регулярных графах и их автоморфизмах 63
3.1 Автоморфизмы графа с параметрами (210,95,40,45).............. 63
3.2 Автоморфизмы графа с параметрами (95,40,12,20)............... 84
3.3 Автоморфизмы точечного графа частичной геометрии р(?2(4, 9) 103
3.4 Автоморфизмы сильно регулярного графа, в котором окрестности вершин являются точечными графами
частичной геометрии рб?2(4.9)................................108
2
Введение
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию (см. [10]-[14], [30], [29]). Например, класс билдингов Титса характеризует группы лиева типа [33]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [10].
Пусть (7 — транзитивная группа подстановок на множестве П. Если стабилизатор Ор в (7 точки р Е П имеет г орбит на Г2, то говорят, что <7 имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г — 3 и соответствующие три орбиты — это {р}, Д(р) и Г(р). Тогда по группе (7 удается построить сильно регулярный граф Г с множеством вершин П, и две вершины р, с/ смежны в Г, если q Е Г(р) [19].
Д. Хигман ([ 19)—[25]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
Грас.]) Г диаметра (I называется дистанционно транзитивным, если для любого г Е {0,...,(1} и для любых его вершин и,и.х,у таких, что (1(щу) = д{х) у) = г, существует автоморфизм у графа Г такой, что (и,у)9 — {х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 (см. [30]). В настоящее время при исследовании графов вовлекаются
3
симметрии псе более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности.
Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах прошлого века. Пусть Ь(Кп) — реберный граф полного графа Кп на п вершинах, или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами — 2),ті — 2,4). В работах 1959-60 годов Л. Чанг [18] и А. Хофф-
ман ((26], [27]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех гг, за исключением п = 8. Для случая п = 8 было показано, что, кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [17].
Через К1Пи_іГПп обозначим полный тг-дольный граф с долями порядков ті,...,тп^. Если Ш\ = ... = тПп = т, то соответствующий граф обозначается через Кпхт• Если тп > 2, то граф К^т называется тп-лапой. Реберный граф Ь(Кт>п) полного многодольного графа Кт>п является кореберно регулярным графом с параметрами (тп, т + п — 2,2). Реберный граф для КтіН называют шхп- решеткой. Известно, что п х п- решетка является сильно регулярным графом с параметрами (7г2,2п — 2, п — 2,2). С. Шрикханде в [32] показал, что сильно регулярный граф, имеющий параметры п х п- решетки является либо п х п- решеткой, либо графом Шрикханде при п = 4.
Результаты Л. Чанга , С. Шрикханде и А. Хоффмана [28] были объединены Дж. Зейделем [31], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что, кроме треугольных графов Т(п) и п х п-решеток, сильно регулярными графами с наименьшим собственным значением —2, являются только графы Кпх2> графы Петерсена, Шрикханде, Клсбша, Шлефли и три графа Чанга.
Основные определения. В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ь - вершины графа Г, то через
4
с1{а,Ь) обозначается расстояние между а и 6, а через Г* (а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Гх(а) называется окрестностью вершины а и обозначается через [о]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом, степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно реггуллрным графом с параметрами (и, к, А), если Г содержит и вершин, является регулярным степени к и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (и, /с, Л, /і), если Г' реберно регулярен с соответствующими параметрами и подграф [а]П[Ь] содержит р вершин в случае сі(а, Ь) — 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Если (1(а,Ъ) = 1, то число вершин в [а] П [Ь] обозначим через А(а, 6), а подграф [а] П [6] назовем А -подграфом. Если с1(а, Ь) — 2, то число вершин в [а] П [6] обозначим через д(а, Ь), а соответствующий подграф назовем р-подграфюм.
Если вершины и, и; находятся на расстоянии г в Г, то через 6;(н, щ) (соотв. Сі(и,т)) обозначим число вершин в пересечении Г*+і(и) (соотв. Гі_і(ц)) с Г(и>). Заметим, что в реберно регулярном графе число Ь\(и,ги) не зависит от выбора смежных вершин и, и) и обозначается через Ь\.
Частичной геометрией р(7а(5,£) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит 5 + 1 точку, каждая точка лежит на і -4-1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой Ь, найдется точно а прямых, проходящих через а и пересекающих Ь. Если а- = 1, то геометрия рСга(б’, £) называется обобщенным четырехугольником и обозначается
адМ).
5
Точечным графом частичной геометрии называется граф. вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Точечный граф частичной геометрии pGa(s, t) сильно регулярен с параметрами v = (s + 1)(1 + st/a), к = s{t Ч- 1), Л =
(s — 1) -f (а — 1 )t, р = a(t 4-1). Любой сильно регулярный граф с такими параметрами для некоторых а, s, t называется псевдогеометрическим графом для pGa(s, t).
Цель диссертации. Целью данной работы является решение следующих задач:
1) изучить связные реберно регулярные графы с параметрами (и, к, Л) и к > 3&i - 1;
2) найти возможные автоморфизмы сильно регулярного графа, являющегося псевдогеометрическим для р<72(4,9);
3) найти возможные автоморфизмы сильно регулярного графа, в котором окрестности вершин являются точечными графами частичной геометрии pG2( 4,9).
Методы исследования. Основными методами исследования являются теоретике-графовые методы, методы локального анализа комбинаторно симметричных графов и методы теории конечных групп, в частности, метод Хиг-мена приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов и подграфов неподвижных точек этих автоморфизмов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следующие.
1. Исследованы связные реберно регулярные графы с параметрами (г>, /с, Л) и к > 3bi — 1.
2. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (210,95,40,45) и (95,40,12,20).
3. Найдены возможные порядки и подграфы неподвижных точек автомор-
б
физмов сильно регулярного графа, в котором окрестности вершин являются точечными графами частичной геометрии рС?2(4,9).
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжют изучение комбинаторно симметричных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Апробация работы. Основные результаты работы докладывались на международном российско-китайском семинаре ( Иркутск, 2007), VII Международной школе конференции по теории групп (Челябинск, 2008) и на 39-Й и 40-й Всероссийских молодежных конференциях ИММ УрО РАН (Екатеринбург, 2008-2009 гг.).
Результаты работы также докладывались и обсуждались на алгебраическом семинаре ИММ УрО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [35]—[41|. Работы [35]—[40] выполнены в нераздельном соавторстве с A.A. Ма.х-иевым.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 41 наименования.
Результаты диссертации.
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе 1 приведены предварительные результаты, необходимые для доказательства теорем, сформулированных в следующих главах.
В главе 2 рассматриваются связные реберно регулярные графы с параметрами (v, к, Л) и к > 3&i — 1.
Пусть Г — реберно регулярный граф с параметрами (и, к. А) и &i = Л:—А—1. Пара вершин и, w называется хорошей (почти хорошей), если d(u,w) = 2 и р.(и, w) равно к—26] -f 1 (равно k—2b\+2). 1 ройка вершин (и, z) называется хорошей (почти хорошей), если w, 2 € Гг(гО и ß(u, w) -f ß(u, z) не больше
7
2/с — 4&i 4- 3 (равно 2к — Abi 4- 4).
В [2, предложение и лемма 1.9], доказано, что если Г — связный рсбсрно регулярный граф диаметра 2 с параметрами (и, /с, Л), где к = 3bi+7 и 7 > —2, то выполняются следующие утверждения:
(1) если Г содержит такую 3-коклику Д, что любые се две вершины образуют хорошие пары, то 7 < —1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2;
(2) если некоторая вершина и графа Г лежит в хорошей паре, то либо 7 < Ь\ — 6, либо bi = 1 и Г — многоугольник, либо &i = 2 и Г — граф икосаэдра или граф с к = 4 диаметра, большего 2;
(3) если 7 > 0 и для некоторой вершины и подг раф Г2(гг) содержит две вершины, образующие хорошие пары с и, то 7 < Ь\/2 — 2.
Уточнение утверждения (2) получено в |6). В параграфе 2.1 доказано предложение 1 о почти хороших тройках, с помощью которого в теореме 1 получено усиление утверждения (3).
Предложение 1 Пусть Г — связный рсбсрно регулярный граф с параметрами (г>, к,Х), к = ЗЬ\ 4- 7 и 7 > 0. Если (u,w, z) — почти хорошая тройка вершин в Г и Д = [гг] П [w] П [z], то верно одно из следующих утверждений:
(1) вершины w,z не смеэю71Ы и | Д | = 0;
(2) вершины w, z смежны и либо
(г) подграф [г*] П [го] П [z] является 2-кликой, 7 = 0, р(и, w) = д(гг, z) — bi 4- 2, Г2М П ([w] U [z]) — {w, z} U ([гг;] П \z\) и bi > 8, либо
(гг) подграф [г/] П [w] П [z] является 3-кликой, 7=1, fi(u, w) — //(гг, z) = bi 4- 3, bi = 3 и Г — граф Клебгиа, либо
(ш) подграф [гг] П [гг>] П [z] является А-кликой, 7=1, ß(u, w) = /г(гг, z) = 61 4- 3, b] = 5 и Г — граф Шлсфли.
Теорема 1 Пусть Г — связный неполный реберно регулярный граф) с параметрами (и, к, А) и к = З61 4- 7, 7 > 0. Если 7 > 56i/12 — 5, то каждая
8
вершина графа Г леоісит не более чем в одной хорошей паре.
В работе Л. Браувера [10] доказано, что если Г связный неполный реберно регулярный граф с параметрами (г>, /с, Л), в котором к > 3то диаметр равен 2 и выполняется неравенство kb\ > (v — к — 1)(к — 26i 4- 1). В статье
A.A. Махнева и Д.В. Падучих [2] эти результаты были уточнены и получена верхняя оценка для числа вершин связного реберно регулярного графа диаметра 2 с параметрами (и, к, Л) и к — З&і 4- 7, 7 > —2. В параграфах 2.5-2.б с помощью результатов о почти хороших тройках эта оценка уточняется для графов с к = 3&1 — 1. Доказана следующая теорема.
Теорема 2 Пусть Г — реберно регулярный граф с к = 3&i — 1, p(u,w) 4-р(и, z) — 2&1 4- 2 для различных w, 2 ш Гг^), Д = [гг] Г) [гг] П [г]. 7огда верно одно из следующих утверждений:
(1) вершины гг, z не смеэюиы и |Д| =0;
(2) А = {а}, ß(u,w) = p(u,z) = b\ + 1, [гг] П [гг] — а*1 содероісит единственную вершину с, [г/] П [z] — а1 содержит единственную вершину е и [ш] и [z] - [и] С {ш, z} и (И Г) [z]);
(3) А является 2-кокликой, [гг] — ([гг] U ^~L) содержит единственную вершину z* и [z] — ([г/.] иггг1-) содерэ/сит единственную вершину гг*;
(4) А является 2-кликой.
Следствие I Пусть Г — связный неполный реберно регулярный граф) с параметрами (г>, А:, Л) и k = 36і — 1. Тогда либо граф Г является многоугольником или графом икосаэдра, либо верно одно из утверждений:
(1) для некоторой вершины и в Г найдутся две вершины гг, z, образуют,ие хорошие пары с и, и либо вершины w,z смео/сны и v < bbi, либо вершины w, z не смежны uv <6Ь і — 8;
(2) в Г пет вершин, лежаищх в двух хороших парах, Г содерэюит хорошую пару и v < 6&1 — б;
(3) в Г нет хороших пар и либо
9
(г) Г пе содержит почти хороших пар и v < 661 — 6, либо (гг) Г содерэюит почти хорошую тройку (и, гс, z), вершины w, z смежны и
v < 56i -f (61 — 3)/2, либо
(ш) Г не содерэюит почти хороших троек (гг, ги, z) со смежными вершинами w, z и v < 6bi — 9 4- 16/(&i 4- 2).
Для конкретных параметров аналогичный результат можно получить при более слабых предположениях.
Теорема 3 Пусть Г — связный реберпо регулярный граф с параметрами к = 17 и Ь\ — 6. Тогда v = 30, и в Г нет хороших и почти хороших пар вершин.
Глава 3 посвящена изучению автоморфизмов дистанционно регулярных графов.
В работе A.A. Махнева [4] доказано, что связный вполне регулярный граф, окрестности вершин которого являются псевдо геометрическим и графами для р£2(4, £) либо является графом Тэйлора, либо сильно регулярен с параметрами (210,95,40,45). В главе 3 с помощью метода Г. Хигмана, приведенного в [15], исследуются возможные порядки элемента в группе автоморфизмов сильно регулярного графа, а также выяснено строение подграфов неподвижных точек автоморфизмов простых порядков сильно регулярных графов с параметрами (210,95,40,45) и (95,40,12,20). Как следствие, доказано, что точечный граф частичной геометрии рСт2(4,9) пе является вершинно симметричным. Кроме того, выяснено строение подграфа неподвижных точек сильно регулярного графа, окрестности вершин которого являются точечными графами частичной геометрии pG?.(4,9).
Пусть Г — сильно регулярный граф, G = Aut(r), g — элемент простого порядка р из G и Q — Fix(g). Для автоморфизма g через оц{д) обозначим число пар вершин (гг, и9) таких, что d.(u, и9) = г.
Основными результатами 3 главы являются теоремы 4-6.
Ю
- Київ+380960830922