Локальное строение графов и их автоморфизмы

• Автор: Падучих, Дмитрий Викторович
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2008
• Место защиты: Екатеринбург
• Количество страниц: 204 с. : ил.

Оглавление

1 Оценка для числа вершин в реберно регулярных графах

1.0.1 Предварительные результаты

1.0.2 Хорошие пары в графах с к > Зїц

1.0.3 Доказательство теоремы 1.1 и следствия

2 Графы без т-корон

2.1 Окрестности вершин — кликовые расширения решеток

2.1.1 Общие результаты

2.1.2 Доказательство теоремы

2.2 Графы без корон с регулярными д-подграфами

2.2.1 Вспомогательные результаты

2.2.2 Доказательство предложения
2.2.3 Графы Тервиллигера без корон
2.2.4 Редуцированные графы без 3-коклик
2.3 Графы без 3-корон с реберно регулярными д-подграфами
2.3.1 Вспомогательные результаты
2.3.2 Доказательство теоремы 2.5 и предложения
2.3.3 Локальная характеризация графов без 3-корон
2.3.4 Восстановление окрестностей
2.4 Несуществование локально ,7(10,5) графов
2.4.1 Предварительные результаты
2.4.2 Локально/(10,5) графы
2.5 Окрестности вершин изоморфны половинному свернутому
10-кубу
2.5.1 Предварительные результаты
2.5.2 Доказательство теоремы
2.6 д-подграфы в локально графах Грассмана
2.6.1 Вспомогательные результаты
2.6.2 Локально (9+1) х т подграфы в графах Грассмана
/?(4,2)

2.6.3 Локально (q + 1) х (q+ 1)-подграфы в графах Грас-
смана Jq(n, 2)
2.7 Вполне регулярный локально J2(n, 2) граф с д
2.8 Вполне регулярные расширения GQ(4,2)
2.8.1 Случай д
2.8.2 Случай д
2.8.3 О вполне регулярных антшюдальных накрытиях клик119
2.8.4 Случай д
3 Кореберно регулярные графы с двумя значениями А
3.1 Предварительные результаты
3.2 Графы с двумя значениями А, в которых д-подграфы являются 2-кокликами
3.3 Графы с Aj
4 Автоморфизмы дистанционно регулярных графов
4.1 Автоморфизмы сильно регулярного графа с параметрами
(85,14,3,2)
4.1.1 Предварительные результаты
4.1.2 Характеры групп и автоморфизмы графов
4.1.3 Инволютивные автоморфизмы графа с параметрами (85,14,3, 2)
4.1.4 Группа автоморфизмов графа с
параметрами (85,14, 3, 2)
4.2 Автоморфизмы графа Ашбахера
4.2.1 Предварительные результаты
4.2.2 Неподвижные точки автоморфизмов графа Ашбахера
4.2.3 Группа автоморфизмов графа Ашбахера, четный случай
4.2.4 Группа автоморфизмов графа Ашбахера, нечетный случай

Введение
Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь — вершины графа Г, то через (1(а, Ь) обозначается расстояние между а и 6, а через Г*(а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии і от вершины
а. Подграф Г] (а) называется окрестностью вершины а и обозначается через [а]. Через ах обозначается подграф, являющийся шаром радиуса 1 с центром а.
Регулярным графом степени к называется Граф Г, такой что для любой вершины и Є Г выполняется !Г(?/.)[ = к. Реберно регулярным графом с параметрами (у, к, А) называется регулярный граф степени к на V вершинах, любое ребро которого лежит точно в А треугольниках. Вполне регулярным графом с параметрами (и, к, А, у) называется реберно регулярный граф с параметрами (г?, /с, А), в котором любые две вершины и, т Є Г на расстоянии 2 имеют ровно у общих соседей. Сильно регулярным графом с параметрами (у, к, А, у) называется реберно регулярный граф с параметрами (л, к, А), в котором любые две несмежные вершины ы, ги Є Г имеют ровно у общих соседей.
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии, и геометрии этого класса можно классифицировать. Например, класс билдингов Титса характеризует группы Лиевского типа [1].
Пусть Є — транзитивная группа подстановок на множестве П. Если стабилизатор точки р Є П имеет г орбит, то говорят, что Є—группа ранга г. Пусть г = 3 и соответствующие 3 орбиты—это {р}, ГДр), Г2(р). Если Гі(р) и Г2(р) содержат разное число элементов, то на множестве П можно построить сильно регулярный граф Г. Для этого положим, что точка р смежна со всеми точками из Гі (р), и для каждого д Є С точка р9 смежна со всеми точками из ГДр)3. Если вместо ГДр) здесь взять Г2(р),

в Г2(гг), для любой вершины у из {w, z, /, д} подграф Хз содержит точно две вершины у', у" несмежных с у, [и] содержит 2 вершины из Хп, 6 вершин из Хз и 8 из Xi, Хз не является кликой, и у{и,у) > 7 для любой вершины у из Г2(и) — {?а, л, /, (/}.
Доказательство. Пусть выполнены условия леммы 1.10. Тогда либо Г2(гг) содержится в wxUлх и 6i(bi — 1) делится на 3, либо Г2(гг) —(гахилх) содержит единственную вершину X И Ь (Ь + 1) делится на 3.
По лемме 1.9 имеем Ьх > 5. Допустим, что Ьх = 5. Тогда Г2(и) — (w1- U г ) содержит единственную вершину х, к = 36х — 2 = 13 и А = 7. Противоречие с тем, что число кХ четно. Утверждение (1) доказано.
Предположим, что Г2(м) — (гах U zх) содержит вершину х. По лемме 1.11 имеем г> - к — 1 — 26х + 3.
Если вершины х, w' несмежны, то [го'] не пересекает [d] П ([ж] U [и]) и y(d, га') = b - 1. В этом случае [z] П [га'] содержит w", и по Ьх — 2 вершин из [гг]П[л] и из [га] П [z — [d]. Ввиду леммы 1.6 получим w" £ [ж]. Заметим, что |Г — (ж1 U (и")"1)! — Ь + 3, причем Г — (жх U (га")х) содержит и, w и Ьг — 1 вершин из [и] П [га]. Поэтому |[га"] П [гг] П [л]| > 6Х — 4 и по лемме
1.6 имеем у(и, W") > Ъ + 1.
Положим у = fi(x,w') и применим лемму 1.13 к тройке {dx,w'). Так как [d] - ([ж] U [«/] содержит и,и> и 6Х — 2 вершин из [и] П [ш], то ввиду леммы 1.13 получим Г2(Д С х1 U (гу')х, v — к — 1 = 26х + 3 = 46х — у и у = 2ЬХ — 3. Если вершины г', z" несмежны с га', то [га] П [га'] содержит г и Ь— 2 вершин вне dx, поэтому у(ъа,га') = 6Х — 1, Г2(га') — (d±UwL) — {ж} и у(х, z) = hi — 1. Противоречие с тем, что [ж] П [г] содержит 6Х — 2 вершин из [d] П [ж] и ие менее 6Х — 3 вершин вне dx. Значит, |[гл'[ П {z1, z"} > 1.
В случае у(и, х] — 6Х — 1 применим лемму 1.10 к тройке (ж;гг, d). Тогда роли гг', гг" играют га, г, роль ж играет ?«' и [d] П [ж] П [гг] = {е}. Но вершины га, га' несмежны, поэтому /г(е, га) = у(е, га') = &х — 1, причем y{w, w') < bi+1. Противоречие с тем, что в этом случае v — k — 1 = 36х — 1 и v = 2к + 2. Итак, у(и, ж) > 6Х. Далее, г', г" е [ж], иначе для вершины z' несмежной с х получим y(d, z') = bi — 1, z' G [w'] и [d] П [z1] не пересекает [гг/], противоречие с леммой 1.12. Если га' £ [z'] — [z"], то y(w,w') = Ъ и [га] П [га'] содержит вершину г, несмежную с z'. Противоречие с тем, что г' смежна с вершиной ж вне гах U (га')х и ее степень в графе [га] П [га'] равна b — 1. Значит, z', z" £ [га'] и [га] П [z] П [га'] С [г'] П ]z"].
Допустим, что вершины z',z" смежны. Тогда [га'] П [z' содержит z", bi — 2 вершин из [га] П [z] и либо га" и Ьх — 3 вершин из [гг] П [га'] — [г], либо Ь — 2 вершин из [гг] П [га'] — [z]. Противоречие с тем, что [z'] П [л"] содержит ж, га, га', 6Х — 2 вершин из [га] П [z] и не менее b | — 3 вершин из {га"} U ([гг] П [га'] — [л]). Значит, вершины z',z" несмежны и [га'] П [z']