Содержание к диссертации
Введение
1 Оценка для числа вершин в реберно регулярных графах 20
1.0.1 Предварительные результаты 22
1.0.2 Хорошие пары в графах с к > ЗЬ\ — 2 26
1.0.3 Доказательство теоремы 1.1 и следствия 1.1 38
2 Графы без т-корон 41
2.1 Окрестности вершин — кликовые расширения решеток . 42
2.1.1 Общие результаты 45
2.1.2 Доказательство теоремы 2.2 49
2.2 Графы без корон с регулярными jU-подграфамй 52
2.2.1 Вспомогательные результаты 54
2.2.2 Доказательство предложения 2.1 58
2.2.3 Графы Тервиллигера без корон 59
2.2.4 Редуцированные графы без 3-коклик 61
2.3 Графы без 3-корон с реберно регулярными /х-подграфами . 63
2.3.1 Вспомогательные результаты 64
2.3.2 Доказательство теоремы 2.5 и предложения 2.2 67
2.3.3 Локальная характеризация графов без 3-корон . 70
2.3.4 Восстановление окрестностей 73
2.4 Несуществование локально J(10,5) графов 75
2.4.1 Предварительные результаты . 76
2.4.2 Локально J(10,5) графы 78
2.5 Окрестности вершин изоморфны половинному свернутому 10-кубу 86
2.5.1 Предварительные результаты 86
2.5.2 Доказательство теоремы 2.8 89
2.6 //-подграфы в локально графах Грассмана 90
2.6.1 Вспомогательные результаты 91
2.6.2 Локально (q +1) х т подграфы в графах Грассмана J,(4, 2) 93
2.6.3 Локально ( + 1) х (q + 1)-подграфы в графах Грас-смана Jq(n, 2) 96
2.7 Вполне регулярный локально /г(и, 2) граф с // = 16 101
2.8 Вполне регулярные расширения GQ(A, 2) 108
2.8.1 Случай // = 8 114
2.8.2 Случай р = 16 118
2.8.3 О вполне регулярных антиподальных накрытиях клик119
2.8.4 Случай /х = 12 120
3 Кореберно регулярные графы с двумя значениями А 128
3.1 Предварительные результаты 132
3.2 Графы с двумя значениями А, в которых /х-подграфы являются 2-кокликами 135
3.3 Графы с Аг = 0 145
4 Автоморфизмы дистанционно регулярных графов 151
4.1 Автоморфизмы сильно регулярного графа с параметрами (85,14,3,2) 153
4.1.1 Предварительные результаты 154
4.1.2 Характеры групп и автоморфизмы графов 156
4.1.3 Инволютивные автоморфизмы графа с параметрами (85,14,3,2) 161
4.1.4 Группа автоморфизмов графа с параметрами (85,14,3,2) 179
4.2 Автоморфизмы графа Ашбахера 180
4.2.1 Предварительные результаты 181
4.2.2 Неподвижные точки автоморфизмов графа Ашбахера 186
4.2.3 Группа автоморфизмов графа Ашбахера, четный случай 189
4.2.4 Группа автоморфизмов графа Ашбахера, нечетный случай 194
Заключение
Выводы
- Графы без 3-корон с реберно регулярными /х-подграфами
- Графы с двумя значениями А, в которых /х-подграфы являются 2-кокликами
- Инволютивные автоморфизмы графа с параметрами (85,14,3,2)
- Группа автоморфизмов графа Ашбахера, нечетный случай
Введение к работе
Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь — вершины графа Г, то через d(a, b) обозначается расстояние между а и 6, а через Г{(а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии г от вершины а. Подграф Гі(а) называется окрестностью вершины а и обозначается через [а]. Через ах обозначается подграф, являющийся шаром радиуса 1 с центром а.
Регулярным графом степени к называется Граф Г, такой что для любой вершины и Є Г выполняется |Г(и)| = к. Реберно регулярным графом с параметрами (г), к, А) называется регулярный граф степени к на и вершинах, любое ребро которого лежит точно в Л треугольниках. Вполне регулярным графом с параметрами (v, к, А, /і) называется реберно регулярный граф с параметрами (v,k,X), в котором любые две вершины и, w Є Г на расстоянии 2 имеют ровно ц общих соседей. Сильно регулярным графом с параметрами (v,k,X,/j) называется реберно регулярный граф с параметрами (v, ft, А), в котором любые две несмежные вершины и, w Є Г имеют ровно и общих соседей.
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии, и геометрии этого класса можно классифицировать. Например, класс билдингов Титса характеризует группы Лиевского типа [1].
Пусть G — транзитивная группа подстановок на множестве Q. Если стабилизатор Gp точки р Є Q имеет г орбит, то говорят, что G—группа ранга г. Пусть г = 3 и соответствующие 3 орбиты—это {р},Гі(р),Г2(р). Если Гі(р) и Гг(р) содержат разное число элементов, то на множестве П можно построить сильно регулярный граф Г. Для этого положим, что точка р смежна со всеми точками из Ті (р), и для каждого д Є G точка р9 смежна со всеми точками из Ті(р). Если вместо Гі(р) здесь взять Г2(р),
то мы получим дополнительный сильно регулярный граф.
Д. Хигман (см. [2, 3]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов и действуют транзитивно на множестве {(и, w) \ и, w Є Г и d(u, w) — і} для любого г < 2. То есть, такие графы являются дистанционно транзитивными графами диаметра 2.
Граф Г диаметра d называется дистанционно транзитивным, если для любого г є {0,..., d} группа Aut Г действует транзитивно на {(и, w) | и, w Є Г и d(u, w) = і}.
Дистанционно регулярным графом с массивом пересечений (Ь0,..., bd-u Су,..., с,*) называется граф диаметра d, в котором для любых вершин и, w Є Г, находящихся на расстоянии г, подграф Г(ги) содержит ровно bi вершин, находящихся на расстоянии г + 1 от и, и ровно сг- вершин, находящихся на расстоянии і — 1 от и. Легко понять, что условие дистанционной транзитивности влечет дистанционную регулярность графа. Таким образом, результаты, полученные для дистанционно регулярных графов, применимы pi к дистанционно транзитивным графам.
Заметим, что сильно регулярный граф с /і > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с d > 2—вполне регулярным графом с к = bo, X — к — Ь\ — \ \\ \i — с^-
Пусть задан класс графов Т. Мы скажем, что граф Г является локально Т-графом, если для любой вершины а Є Г имеем Г(а) Є Т. Тогда можно поставить задачу описания локально JF-графов. Если граф Г вершинно транзитивен, то окрестности всех его вершин изоморфны, и граф Г является локально Т графом, где Т состоит из графов, изоморфных некоторому графу Д. В этом случае назовем Г локально А-графом. В более общем случае J- может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных, реберно регулярных графов—это в точности класс связных, локально регулярных графов.
Определим несколько сильно регулярных графов, которые будут фигурировать в диссертации, а также являются примерами локально А графов.
Пусть М и N—конечные множества порядка тип, соответственно. Два элемента из М х N будем считать смежными, если они различаются точно в одной координате. Полученный граф называется тп х п-решеткой; при т — п он сильно регулярен с параметрами (п2, 2(п — 1),п-2,2).
Треугольным графом Т(п) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда,
когда они пересекаются в точности по одной точке. Граф Т(п) также сильно регулярен и имеет параметры (п(п—1)/2, 2(77.-2), п—2,4). Окрестность каждой вершины в Т(п) изоморфна 2 х (п — 2)-решетке, т.е. Т(п)— локально 2х(н- 2)-решетка.
Единственный сильно регулярный граф с параметрами (27,16,10,8) называется графом Шлефли. Единственный сильно регулярный граф с параметрами (16,10, 6, 6) называется графом Клебша. Граф Шлефли является локально графом Клебша.
В главе 1 (см. также [51]) получена новая оценка для числа вершин в реберно регулярных графах. В [12, лемма 4.2.1] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (v, к, А), в котором к > ЗЬі, то диаметр Г равен 2 и выполняется неравенство
кЬг > (v-k-l)(k-2b1 + l).
Полученные в главе 1 результаты позволяют уточнить эту оценку.
Пусть a, b — вершины графа Г. Число вершин в [а] П [Ь] обозначим через Х(а,Ь) (через ц(а, Ь)), если d(a,b) = 1 (если d(a,b) = 2), а соответствующий подграф назовем Х-подграфом (ц-подграфом).
Пусть Г — реберно регулярный граф с параметрами (v, к, А) и Ь\ — к — А — 1. Пара вершин и, w называется хорошей (почти хорошей), если d(u, ю) = 2и и(и, w) равно к — 2bi + 1 (равно к — 2bi + 2). Тройка вершин (u;w,z) называется хорошей (почти хорошей), если w,z Є Г2(и) и fi(u, w) + fi(u, z) не больше 2к — Ab\ + 3 (равно 2к — Ab\ + 4).
Через Кти...,тп обозначим полный п-дольный граф, с долями порядков т\,...,тп. Если ті — ... = тп = тп, то соответствующий граф обозначается через Кпхт- Граф /С1)3 называется 3-лапой.
Если вершины и, w находятся на расстоянии г в Г, то через bi(u,w) (через Ci(u,w)) обозначим число вершин в пересечении Гі+і(и) (пересечении Гі_і(и)) с [w]. Заметим, что в реберно регулярном графе с параметрами (v,k,X) значение b\(u, w) не зависит от выбора ребра {и, w} и равно к — А — 1.
Теорема 1.1. Пусть Г — связный неполный реберно регулярный граф с параметрами (v, к, X) и к > Зйі — 2. Тогда выполняется одно из следующих утверждений:
для любой вершины w верно неравенство |Гг(г^) j(/с — 26i + 2) < kb\;
для любой вершины w верно неравенство \T2(w)\(k — 2bi + 2) > kb\ и либо Г является реберным графом тривалентного графа без треугольников (т.е. к = 4, Л = 1) и диаметр графа Г больше 2, либо Г является п-уголъником, п>Ъ, или графом икосаэдра;
(3) Г является полным многодольным графом КГХ2, 3x3 решеткой, треугольным графом Т(т), т < 7, графом Клебша или графом Шлефли и для любой вершины w верно равенство |Г2(гу)|(А; — 2bi + 2) = kb\.
Доказательство утверждения (2) теоремы из [33] некорректно (не доказано утверждение (3) из [33, лемма 3.3]). Следующий результат уточняет данное утверждение.
Предложение 1.1. Пусть Г — связный реберно регулярный граф диаметра 2 с параметрами (v, k,X) и к — ЗЬ\ + 5, 5 > —2. Тогда выполняются следующие утверждения:
если Г содержит такую 3-коклику Д, что любые ее две вершины образуют хорошие пары, то S = — 1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2;
если 5 > 0 и для некоторой вершины w подграф T2(w) содержит две вершины, образующие хорошие пары с ги, то 5 < Ьу/2 — 2;
если для некоторой вершины ги подграф Г2(и>) содержит три вершины f,u,z, образующие хорошие пары с w, то 5 = —2, v — к — 1 = 2Ь\ + 2, bi(bi — 1) делится на 3, подграф {f,u,z} является кликой, для х Є {/, и, z} подграф Г2(го) П Г2(ж) содержит две вершины х',х", для различных вершин х, у Є {/, и, z) подграф [w] П [х] П [у] содержит единственную вершину ху, граф {fu, uz, fz} является кликой и \ [ги] —
(ЇЛ U[u]U Ы) 1 = 4;
(4) если для некоторой вершины w подграф Г2(ги) содержит четыре
вершины {и, z, /, дУ, образующие хорошие пары с w, то b\ = 6, k = 16,
Л = 9, v = 31, подграф {и, z, f, g} является кликой и /j,(w, у) > 7 для
любой вершины у из Г2(ги) — {гг, z, f, g}.
Имеется немного результатов о единственности сильно регулярного графа с данными параметрами (v,k,\,n). В качестве следствия теоремы 1.1 получена единственность некоторых реберно регулярных графов с данными параметрами (v,k,X).
Следствие 1.1. Пусть Г — реберно регулярный граф, имеющий те оісе параметры (v,k,X), что и один из следующих графов: полный многодольный граф KrXs, 3x3 решетка, треугольный граф Т{т), т < 7, граф Клебша или граф Шлефли. Тогда Г изоморфен соответствующему графу.
Графы без 3-корон с реберно регулярными /х-подграфами
Пусть а, Ъ — вершины графа Г. Число вершин в [а] П [Ь] обозначим через Х(а, Ь) (через fi(a,b)), если d(a,b) = 1 (если d(a,b) = 2), а соответствующий подграф назовем Х-подграфом (ц-подграфом). Пусть Г — реберно регулярный граф с параметрами (г , к, А) и Ь\ — к — Х — 1. Пара вершин и, w называется хорошей (почти хорошей), если d(u,w) = 2 и fi(u,w) равно Л; — 26г Ч- 1 (равно к — 2Ь\+2). Тройка вершин (u;w,z) называется хорошей (почти хорошей), если w,z Є Г2(м) и ц(и, W) + fi(u, z) не больше 2к — 4Ьі + 3 (равно 2к — Ab\ + 4). Через -K"mil...,m„ обозначим полный п-дольный граф, с долями порядков mi,...,mn. Если ту = ... = тп = т, то соответствующий граф обозначается через Кпхт. Граф К\ 3 называется 3-лапой. Треугольным графом Т(т) называется граф с множеством неупорядоченных пар из X в качестве вершин, \Х\ = т и две пары {а, Ь}, {с, d} смежны тогда и только тогда, когда они имеют общий элемент. Граф на множестве вершин X х Y называется т х п-решегпкой, если \Х\ = m, \Y\ = п и вершины (х\, у-\), (х2, у і) смежны тогда и только тогда, когда х\ — X2 или у\ = У2- Для подграфа Д через А обозначим число его вершин а через ХІ(А) обозначим множество вершин из Г — А, смежных точно с г вершинами из А. Если вершины и, w находятся на расстоянии г в Г, то через b{(u,w) (через ci(u,w)) обозначим число вершин в пересечении ГІ+І(М) (пересечении Гг_і(и)) с [w]. Заметим, что в реберно регулярном графе с параметрами (v,k,X) значение bx(u,w) не зависит от выбора ребра {u,w} и равно к — X — 1. В [12, лемма 4.2.1] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (v, к,Х), в котором к ЗЬ\, то диаметр Г равен 2 и выполняется неравенство kbx (v-k-l)(k-2bi + l). Теорема 1.1 Пусть Г — связный неполный реберно регулярный граф с параметрами (v, к, X) и к ЗЬ\ — 2. Тогда выполняется одно из следующих утверждений: (1) для любой вершины w верно неравенство Г2(ад)(А; — 2Ьг+2) kbi; (2) для любой вершины w верно неравенство Г2(го)(А; — 2bi +2) kb\ и либо Г является реберным графом тривалентного графа без треугольников (т.е. к — 4, Л = 1) и диаметр графа Г больше 2, либо Г является п-угольником, п Ъ, или графом икосаэдра; (3) Г является полным многодольным графом КГХ2, 3x3 решеткой, треугольным графом Т(т), те 7, графом Клебша или графом Шлефли и для любой вершины w верно равенство r2(w;)(/c — 2bi + 2) — kb\. Доказательство утверждения (2) теоремы из [33] некорректно (не доказано утверждение (3) из [33, лемма 3.3]). Следующий результат уточняет данное утверждение. Предложение 1.1 Пусть Г — связный реберно регулярный граф диаметра 2 с параметрами (v, к, X) и к = 3bi + 5, S —2. Тогда выполняются следующие утвероюдения: (1) если Г содержит такую 3-коклику А, что любые ее две вершины образуют хорошие пары, то 6 — —1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2; (2) если 6 0 и для некоторой вершины w подграф T2(w) содержит две вершины, образующие хорошие пары с w, то 5 Ь\/2 — 2; (3) если для некоторой вершины w подграф Гз(ги) содержит три вершины f,u,z, образующие хорошие пары с w, то 5 — —2, v — к — 1 = 2bi + 2, bi(bi — 1) делится на 3, подграф {f,u,z} является кликой, для х {f,u,z} подграф T2(w) П Г2(х) содержит две вершины х ,х", для различных вершин х, у Є {/, и, z} подграф [w] П [х] П [у] содероісит единственную вершину ху, граф {fu, uz, fz) является кликой и \ [w] — ([/]U[«]Ufo]) = 4; (4) если для некоторой вершины w подграф Г2(го) содержит четыре вершины {и, z, /, д}, образующие хорошие пары с w, то Ь\ = 6, к — 16, X = 9, v — 31, подграф {и, z, /, g} является кликой и fi(w, у) 7 для любой вершины у из Г2(-ш) — {и, z, /, д}. Следующий пример показывает, что для графа Г с к ЪЬ\ — 3 и его вершины w подграф Г2(гу) может содержать к вершин, образующих хорошие пары с и. Пример. Пусть Ап — граф, вершинами которого являются 4-циклы из Sn и два цикла а, Ь смежны тогда и только тогда, когда ab является 5-циклом. Тогда А5 является реберно регулярным графом диаметра 3 с параметрами (30,12,6) и каждая вершина из [(1432)] образует хорошую пару с (1234). Имеется немного результатов о единственности сильно регулярного графа с данными параметрами (v, к, А, д). В качестве следствия теоремы 1.1 получена единственность некоторых реберно регулярных графов с данными параметрами (v,k,X). Следствие 1.1 Пусть Г — реберно регулярный граф, имеющий те же параметры (v,k,\), что и один из следующих графов: полный многодольный граф КгХя, 3x3 решетка, треугольный граф Т(т), тп 7, граф Клебша или граф Шлефли. Тогда Г изоморфен соответствующему графу. 1.0.1 Предварительные результаты В этом параграфе доказано несколько вспомогательных утверждений. Лемма 1.1 Пусть Г — реберно регулярный граф с параметрами (v,k,\) иЪЛ = к — А — 1. Если вершины и, w находятся на расстоянии 2 в Г, то выполняются следующие утверждения: (1) степень любой вершины в -подграфе из Г не меньше к — 2Ь\; (2) вершина d имеет степень а в графе [и] П [w], тогда и только тогда, когда [d] содержит а — (к — 2bi) вершин вне и1- U гих; (3) если и(и, w) — к — 2bi + 1, то подграф [и] П [w] является кликой и [d] С их U W1- для любой вершины d Є [и] Г) [w]; (4) если Г—(мхиги±) содержит единственную вершину z, то ц(и, z) — u(w,z). Доказательство. Пусть d Є [и] П [w]. Тогда \[d] — и1-] = \[d] — w1-] = bj.. Поэтому по крайней мере к — 2Ьг вершин из [d] содержится в [и] П [w]. Утверждение (1) доказано. Пусть d Є [и] П [w] и степень d в этом д-подграфе равна а. Тогда к = a + 2bi — \[d] — (и1- U wx). Поэтому [d] содержит а— (к — 2Ьг) вершин вне их U wL. Утверждение (2) доказано. Утверждение (3) следует из (1), (2). Пусть {z} = Г — (и1- U w1). Так как число ребер между [и] — [w] и [w] — [и] равно bi\[u] — [w]\— ц{и, z), то и(и, z) — /i(w, z). Лемма доказана. Лемма 1.2 Пусть Г — сильно регулярный граф, имеющий параметры (v,k,X,fj,). Тогда либо к = 2ц, X = р, — 1 ( так называемый половинный случай), либо неглавные собственные значения п — т, —т графа Г — целые числа, где га2 — (А — /І)2 + 4(к — /г), га — А + = 2т и кратность k(m-l)(k + m) п — т равна . Далее, если т — целое число, большее 1, fin то т — 1 делит к — X — 1 и
Графы с двумя значениями А, в которых /х-подграфы являются 2-кокликами
Пусть выполнены условия леммы 1.10. Тогда либо Г2(и) содержится в гохиг± и 6i(&i — 1) делится на 3, либо Г2(гі) — (w±Uz±) содержит единственную вершину х и biipi + 1) делится на 3. По лемме 1.9 имеем Ь\ 5. Допустим, что Ь\ = 5. Тогда Г2(и) — (w1- U z-1) содержит единственную вершину х, k = 3&1 — 2 — 13 и Л = 7. Противоречие с тем, что число кХ четно. Утверждение (1) доказано.
Предположим, что Г2(и) — (w1- U z1-) содержит вершину х. По лемме 1.11 имеем v — к — 1 = 2&i + 3. Если вершины x,w несмежны, то [го ] не пересекает [d] П ([ж] U [и]) и /j,(d, w ) = &i — 1. В этом случае [z] П [го ] содержит го", и по Oi — 2 вершин из [гі]П[г] и из [го]Г)[,г] — [d]. Ввиду леммы 1.6 получим го" Є [х]. Заметим, что Г — (х1 U (го")-1)! = by + 3, причем Г — (ат1 U (го")-1) содержит и,го и oi — 1 вершин из [и] П [го]. Поэтому \[w"] П [и] П [z]\ 61 — 4 и по лемме 1.6 имеем fi(u, w") 61 + 1. Положим д = //(а;, го ) и применим лемму 1.13 к тройке (d; х, w ). Так как [d] — (И U [го ] содержит и, го и Ь\ — 2 вершин из [и] П [го], то ввиду леммы 1.13 получим Г2(гі) С жх U (го )-1, г» — А; — 1 = 2&i + 3 = 46і — /І и /І = 2&1 — 3. Если вершины г , г" несмежны с го , то [го] П [го ] содержит г и »1—2 вершин вне с/х, поэтому гх(го,го ) = &i — 1, Г2(го ) — (d±Uw±) = {ж} и а(х, z) — b\ — 1. Противоречие с тем, что [х] П [г] содержит 6i — 2 вершин из [d] П [ж] и не менее &i — 3 вершин вне dL. Значит, [го ] П {z1, z"}\ 1. В случае ц(и,х) = 01—1 применим лемму 1.10 к тройке (х;и,d). Тогда роли и , и" играют го, z, роль х играет го и [d] П [х] П [г ] = {е}. Но вершины го, го несмежны, поэтому /г(е, го) = /г(е, го ) = &i — 1, причем //(го, го ) »1+1. Противоречие с тем, что в этом случае v — к — 1 = Зої — 1 и г = 2к + 2. Итак, и(и, х) Ь\. Далее, z , z" Є [х], иначе для вершины z несмежной с х получим /i(d, z ) = b\ — 1, z Є [го ] и [d] П [г ] не пересекает [го ], противоречие с леммой 1.12. Если го Є [z \ — \z"], то /J,(W,W ) = Ьі и [?/;] П [го ] содержит вершину z, несмежную с z . Противоречие с тем, что z1 смежна с вершиной х вне гох U (го )-1 и ее степень в графе [го] П [го ] равна oi - 1. Значит, z , z" Є [го ] и [го] П [z] П [г//] С [г/] П [z"\. Допустим, что вершины z\ z" смежны. Тогда [го ] П [z ] содержит z", 01—2 вершин из [го] П [г] и либо го" и ог — 3 вершин из [и] П [го ] — [z], либо &1 — 2 вершин из [и] П [го ] — [z]. Противоречие с тем, что [z \ П [z"] содержит ж, го, го , bi — 2 вершин из [го] П [г] и не менее Ь\ — 3 вершин из {го"} U ([и] Г) [го ] — [z]). Значит, вершины z , г" несмежны и [го ] П [z;] содержит w" и по Ъ\ — 2 вершин из [гу]п[.г] и из [и]П[гу ] — [z]. В частности, вершины z\ z" несмежны с е. Так как [w] П [z \ содержит 6г — 2 вершин из [it/] П [z], то [d] П [-г ] содержит w и &i — 1 вершин из [гу]. Симметрично, [d] П [г"] содержит гу и 6i — 1 вершин из [гу]. Теперь тройка (c?;z ,z") является почти хорошей и \[d] П [г ] П [г"] 3, противоречие с леммой 1.7. Итак, w ,w",z ,z" Є [х]. Пусть іл(и,х) — Ь\ — 1. Тогда тройку (к;гу,2;) можно заменить на (x;u,d), причем в роли вершин и ,и" выступают w, z и [w] П [z] не пересекает [и] П [d] - {е}. Положим Т2(х) - (и1 U rf-1) = {/}. Тогда [е] П [/] содержит верпшну д из [х] — [и] и Ьх — 2 вершин из [е] П [и] П [d]. Как показано выше, [/] содержит обе вершины d ,d" из [и] — (dL U [х]) и не менее 2Ъ\ — 7 вершин из [и] Г) [d]. Если [/] содержит w ,w",z ,z", то, без ограничения общности, [/] содержит не менее Ь\ — 3 вершин из [и] П [ги]. Противоречие с тем, что [/] — zL содержит d ,d",z ,z" и не менее Ь\ — 3 вершин из [и] П [гу]. Если [/] содержит 3 вершины из {w , ги" , z , z"}, скажем, {гу , гу", г }, то [/] содержит не менее 2&і — 6 вершин из [и] n[d]. В этом случае [/] — гух содержит d , d", гу , гу" и Ь\ — 4 вершин из [и] П [г]. Поэтому [/] — z1- содержит d , d", z и Oi — 2 вершин из [гі] П [гу], противоречие. Значит [/] содержит 2 вершины из {и/, гу", г , г"} и 2&і — 5 вершин из [и] П [d]. Можно считать, что [/] содержит &1 — 2 вершин из [и] П [г]. Тогда [/] содержит z ,z" и 01—3 вершин из [it] П [гу], противоречие. Заметим, что Г — (x-LU(w )L) содержит и,ги и 6i — 1 вершин из [ІІ]П[ІУ], поэтому [гу ] содержит не менее 6і — 4 вершин из [и] П [г]. Далее [гу ] — .г1-содержит х, не более двух вершин из {z1, z"} и не менее &1 — 3 вершин из [и] — [г], поэтому ц(и,ги ) 2Ъ\ — 7. Утверждение (2) доказано. Пусть LI(U, /) = &1 — 1 для некоторой вершины / из Г2(ІІ) — {w,z}. Предположим сначала, что Г2(г ) — (w Uz-1) содержит вершину х. Тогда по лемме 1.6 имеем ц(и,х) = Ь\ + 1 и / Є [х]. Ввиду утверждения (2) имеем / Є [w] ҐІ [г]. Если [/] не пересекает [и] П [гу], то по лемме 1.12 имеем v — к — 1 = 201 + 1, противоречие. Поэтому [и] Г) [/] содержит вершину а из [гу] и вершину о из [г]. Если а = сі, то степень d в графе и не меньше 3(&i — 2), противоречие. Поэтому подграф {d, а, Ь} является 3-кликой. Так как [/] — хх содержит две вершины из [и] и не более пяти вершин из Г2(г/.), то b\ = б. Теперь [ж]пГ2(гі) содержит /, гу , гу", z , z" и 4 вершины из [й]П[гу]П[,г], в частности Ми 2/) &1 Для любой вершины у Є Г2(гг) — {/, ги, z}. Заметим, что Г2(и) — {f,w,z}\ = 2Ъ\ = 12, число ребер между [и] и Г2(и) —{/, ги, z} равно 81 и 12-7 = 84. Поэтому Г2(и) содержит 3 вершины Уі,У2,Уз с и(и,Уї) — 6- Заменив троку (u;w,z) на (u;w,f), получим вершину ги в роли ж, ги" Є [/] и [гу] П [z] П [/] = 2ох — 6 = 6. Заменив троку (u;w,z) на (u;z,f), получим вершину z в роли х, z" Є [/] и вершину х в роли/ (f"E[w]n[z]). Если уі Є [го] П [z] П [/], то [уі] П [гу2] содержит не менее двух вершин из [и] П [х] и две вершины из {/, w,z}. Противоречие с леммой 1.7. Значит, {Уі,У 2,Уз} = {w",z",f"} и [го"] П [z"\ П [/"] содержит все 4 вершины из [и] — ([го] U [z] U [/]). Теперь [/"] содержит х и по вершине из [и] П [го] и из [г ]П[ ]. Поэтому [/"] не пересекает {го , го", z , г"}, противоречие с тем, что по лемме 1.11 число [/"]П{го ,го",г ,г"} нечетно. Итак, Г2(и) С го и , утверждение (3) доказано. Допустим, что Т2(и) — {го, z} содержит 2 вершины f,g с /i(u, /) = /х(гх, д) = bi 1. Тогда [и] П [д] содержит по вершине из [го], [г], [/] и 6i — 4 вершин из [и] — ([го] U [z] U [/]), поэтому Ь\ 8. Но 8 7 не делится на 3, поэтому 6i = 6, к = 16, Л = 9 и v = 31. Пусть Xj — множество вершин из Г — {w,z, /, д}, смежных точно с г вершинами из {го, z, /, д}, Х{ = \ХІ\. Тогда подграф {го, z, f,g} является кликой, Х\ = {1,т} содержится в Г2(и), для любой вершины у из {w, z, f, д}, подграф Хз содержит точно две вершины у , у" несмежных с у, XQ — {r,s} содержится в [и], и [и] содержит 6 вершин ИЗ Х-}, и 8 из Х\. Для двух вершин х,у из {w,z,f,g} через ху обозначим единственную вершину из [и] П [х] П [у] (например, d — wz). Заметим, что [d] — и1-содержит w,z и 4 вершины из {l,m, f ,f",g ,g"}, a ([d] П [го/]) — и1- содержится в {w,l,m,g ,g"}. Если вершины d, /g смежны, то [d] П [/#] содержит вне и1- лишь I, то, в и1- вершины е, и, fw, gw, fz, gz и вершину из М П [fg] - ([/] U [д]). Если Х2 — клика, то [и] П [г] = Л\ U {s} и [г] П [s] содержит и, 8 вершин из Х\ и не менее 2 вершин из Г2(г{), противоречие.
Инволютивные автоморфизмы графа с параметрами (85,14,3,2)
Пусть Е является кликовым расширением 2-пути. Для двух несмежных вершин и, w из Е содержащая а связная компонента из Г(и)Г\Г(ги) является (А + 2)-кликой. Поэтому v — А + 2 или v 2А + 4.
Пусть b Є Г2(а). Если подграф [а] П [6] содержит вершину с из Ех, то либо v = А + 2, либо с — единственная вершина из Ех П [а] П [Ь] и [а]П[Ь] —{с} является объединением двух изолированных (А + 1)-клик. В последнем случае получим противоречие с тем, что v 2А 4- 4. Если же [а] П [Ь] не пересекает Т,х, то либо снова v = А + 2, либо [а] П [Ь] является объединением двух изолированных (А + 2)-клик.
Если v = А + 2, то Г является графом Тервиллигера и, как показано выше, окрестность любой вершины из Г является либо кликой, либо кликовым расширением 2-пути, пятиугольника или пятиугольной пирамиды. Снова по теореме 1 из [43] либо выполняется одно из утверждений (1-2) в заключении леммы, либо граф Г является кликовым расширением графа без 3-лап с fi = 1. Покажем, что в этом случае и граф Г является кликовым расширением графа без 3-лап с fi = 1. Пусть для вершин и, w из Г шары радиуса 1 в графе Г с центрами в этих вершинах совпадают и некоторая вершина ж Є Г принадлежит [w] — гг1. Тогда [it] П [х] = Г" П [х] является и -кликой. Заметим, что для у Є ([и] П [х]) — Г (и)-1 получим Т (у) С гг1, иначе [у] содержит 3-коклику. Если ([и] П [х]) — Г (и)1- содержит вершину у, то шары радиуса 1 в графе Г с центрами в и и в у не совпадают, поэтому некоторая вершина z Є Г (и) не принадлежит ух. Противоречие с тем, что тогда [ж]П[;г] содержит w и [а;]П[ ] v . Значит, [и] П [х] С Г (и)-1- и подграф {и} U Г (м) является КЛИКОЙ, совпадающей с {е} U Г (е) для є Є Г (и) — [х]. Противоречие со связностью графа Г .
Пусть v = 2А +4. Тогда для любой вершины b из Г2(а) подграф [а]П[6] является объединением двух изолированных (А + 2)-клик. В частности, для с Є [а] П [Ь] подграф Г (с) является графом Тервиллигера. Теперь по связности Г получим, что окрестность каждой вершины — граф Тервиллигера без 3-коклик, и каждый /і-подграф является объединением двух изолированных (А + 2)-клик. Значит, Г не содержит 3-лап и по теореме из [18] редукция графа Г является кликовым расширением тпхп решетки или графа N(m). В первом случае Г является (А /2 + 1)-расширением. Так как в графе N(m) каждый /-подграф является изолированной вершиной или m-кликой, то второй случай не возникает. Лемма 2.37 Пусть является кликовым расширением пятиугольника или пятиугольной пирамиды. Тогда Г является кликовым расширением графа икосаэдра. Доказательство. Пусть Е является кликовым расширением пятиугольника или пятиугольной пирамиды. Тогда для любых двух несмежных вершин с, d Є Е окрестность а в подграфе [с] П [d] является изолированной (А + 2)-кликой. Поэтому для любой вершины Ь Є Г2(а) подграф [а] П [Ь] не содержит несмежных вершин. В этом случае v = А 4- 2 и Г является графом Тервиллигера. Ввиду леммы 2.36 окрестность каждой вершины является кликовым расширением пятиугольника или пятиугольной пирамиды. Таким образом, Г является графом Тервиллигера без 3-лап. По теореме 1 [43] Г является кликовым расширением графа икосаэдра. Лемма и теорема 2.5 доказаны. До конца параграфа будем предполагать, что Г является слабо редуцированным, но не редуцированным графом без корон, в котором fi-подграфы регулярны степени а, а 0. Тогда Ь1- С а для некоторых a, b Є Г. Ясно, что [Ь] не содержит 3-коклик (мначе Г содержит корону). Среди вершин х со свойством хх С ах выберем вершину b наибольшей степени. Ввиду предложения [43] можно считать, что Г содержит 3-лапу. Лемма 2.38 Выполняются следующие утверждения: (1) если вершина х из [Ь] — {а} смежна с вершиной вне ах, то [х] не пересекает [а] — Ьх; (2) подграф [Ь] не является кликой. Доказательство. Пусть вершина х смежна с вершиной с вне ах и вершиной d из [а] —ft-1. Если вершины с, d смежны, то в графе [Ь]П[с] степень вершины х равна а. Противоречие с тем, что в графе [а] П [с] вершина х смежна еще с d. Значит, любая вершина из [х] — ах не смежна ни с одной из вершин в ([х] П [а]) — Ьх. Тогда [х] П [с] П [d] не пересекает Г — ах и [a] — Ьх. Так как а 0, то [х] П [с] П [d] содержит вершину у из [Ь]. Проти воречие с тем, что тогда Г содержит корону {х;у; Ь, с, d}. Утверждение (1) доказано. Пусть [Ь] — клика. Тогда для любой вершины d из [а] — Ьх подграф [b] П [d] является (о; + 1)-кликой. Пусть х Є ([b] П [d]) — {а}. В силу выбора вершины b подграф [х] не содержится в ах, противоречие с утверждением (1). Лемма 2.39 Для любых двух несмежных вершин с, d из [Ь] подграфы [c] и [d] пересекают [а] — Ьх. Доказательство. Допустим, что c,d несмежные вершины из [Ь] и [d] не пересекает [a] —ft1. Если є Є ([а]П[с]) — Ьх, то подграф [d]n[e] содержит а +1 вершин из а1-, попадающих в [Ь]. Противоречие с тем, что в графе [Ь] Г) [е] вершина а смежна еще с вершиной с. Значит, и [с] не пересекает [а] - Ь\ Для є Є [а] — Ьх по утверждению (1) леммы 2.38 подграф [с] П [е] является (а+ 1)-кликой из [Ь]. Симметрично, подграф [d] П [е] является (а+1)-кликой из [Ь], причем [с]П[ і]п[е] содержит единственную вершину а. Противоречие с тем, что тогда степень а в графе [Ь] П [е] равна 2а. Лемма 2.40 Выполняются следующие утверждения: (1) [х] С [о] для любой вершины х Є bx и а — единственная среди вершин х из Г со свойством Ьх С хх; (2) [Ь] — {а} является (а — 1)-расширением пятиугольника; (3) а = 2 и каждая вершина из [а] — Ьх смежна с ребром пятиугольника [Ь] — {а}. Доказательство. Заметим, что ввиду лемм 2.38, 2.39 окрестности любых двух несмежных вершин с, d из [Ь] попадают в ах. Если же Ь1- С е1-для некоторой отличной от а вершины е, то по выбору вершины b подграф [е] содержит вершину / вне а-1. В этом случае [Ь] П [/] является (а-Ы)-кликой, состоящей из вершин е таких, что 6х С ех. Противоречие с тем, что тогда Г содержит (а+ 1)-корону {[Ь] П [/]; с, d, /}. Утверждение (1) доказано.
По утверждению (1) для любых двух несмежных вершин с, d из [Ь] подграф [c]n[cf] является (а + 1)-кликой из а-1. Тогда [c]n[d] С bL. Таким образом, [Ь] является графом Тервиллигера. По теореме 1 [43] граф [Ь] является кликовым расширением 2-пути или пятиугольной пирамиды. В первом случае по утверждению (1) [Ь] — {а} состоит из двух изолированных клик иа=1. Отсюда [а] является графом Тервиллигера диаметра 2 без 3-лап с /І = 1. Снова по теореме 1 [43] граф [а] является пятиугольником {Ь, с, е, /, off. Если [е] — а1 содержит вершину д, то вершина е изолирована в [с] П [д], противоречие. Итак, Г = аА. Противоречие с тем, что Г содержит 3-лапу. Значит, граф [Ь] — {а} является кликовым расширением пятиугольника. Если с, d — две несмежные вершины из [Ь], то степень b в графе [с] П [d] равна а, поэтому граф [Ь] — {а} является (о; — 1)-расширением пятиугольника. Утверждение (2) доказано.
Группа автоморфизмов графа Ашбахера, нечетный случай
Ввиду леммы 2.52 нам нужно доказать, что утверждение верно для произвольных вершин х Є Г2(а) и d Є [х] П Ко([х,а\). Согласно лемме 2.48 мы можем построить подграф [х] по решетке [х, Ь]. При этом с точностью до выбора координат на [х, Ь] можно считать, что октаэдр [ж, а] состоит из вершин четырехугольника (1,2; 1,2), самого четырехугольника (1, 2; 1, 2) и вершины Ь. Так как вершина d не смежна ни с одной из вершин [ж, а], то соответствующий d четырехугольник не пересекает (1,2; 1, 2) и имеет с ним по крайней мере одну общую прямую. Пусть сначала четырехугольники d и (1, 2; 1, 2) имеют ровно две общие прямые. Без ограничения общности будем считать, что вершина d совпадает с (3,4; 1,2). По определению Д(ж) есть [х П [d] П ([ж, а]). Таким образом нетрудно вычислить А (ж).
Прежде всего заметим, что Д(ж) содержит вершины из (3,4; 1,2), а остальные вершины из Д(ж) являются четырехугольниками, которые с одной стороны смежны с (3,4; 1,2), а с другой — пересекают или смежны с (1,2; 1,2). Очевидно, не существует четырехугольников, изолированных и от (1,2; 1,2), и от (3,4; 1,2). Четырехугольников, которые были бы изолированы от одного из (1, 2; 1, 2) и (3,4; 1,2) и пересекали другой, тоже не существует. Остаются четырехугольники (1,3; 1,2), (2,3; 1,2), (1,4; 1,2) и (2,4; 1,2). Таким образом граф Д(ж) содержит ровно 8 вершин. Следовательно, по лемме 2.53 граф Д(ж) изоморфен Е.
Пусть теперь четырехугольники d и (1, 2; 1, 2) имеют точно одну общую прямую. Тогда с точностью до выбора координат на [ж, Ь] можно считать, что d — четырехугольник (3,4; 1,3). По аналогии с предыдущим абзацем находим, что А(ж) содержит вершины из (3,4; 1,3) и следующие четырехугольники: (1,3; 1,3), (1,4; 1,3), (2,3; 1,3), (2,4; 1,3), (3,4; 3,4), (3,4; 3, 5). Таким образом граф А(х) содержит по крайней мере 10 вершин, и, следовательно, по лемме 2.53 изоморфен Г. Лемма доказана.
Скажем, что вершина х из Д имеет тип Е (тип Т), если подграф А(х) изоморфен подграфу Е (изоморфен Т) из леммы 2.49. Лемма 2.55 Пусть х — вершина типа Е. Тогда выполняются следующие утверждения: (1) {х} U А(х) содержится в подграфе Т = Тх из А, изоморфном Т(б); (2) если Т содержит вершину типа Т, mo х — единственная вершина из Т, имеющая тип Е; (3) если Т не содержит вершин типа Т, то Т = Д. Доказательство. Имеется биекция между вершинами октаэдра [а] П [х] и четырехугольниками подграфа А(х), при которой вершине Ъ Є [а] П [х] соответствует четырехугольник [Ь] П [х] П [d]. Поэтому каждый четырехугольник из А(х) вкладывается в октаэдр, лежащий в [d]. В результате получим подграф, содержащий х, А(х) и 6-вершинный подграф, соответствующий четырехугольникам из А(х), и изоморфный Г(6). Утверждение (1) доказано. Допустим, что А(х) содержит вершину у типа Т. Тогда Т{у) содержит 2x3 подрешетку, состоящую из вершин типа Т. Значит, любая 5-клика из Т, содержащая вершину типа Е, либо состоит из вершин типа Е, либо содержит единственную вершину типа Е. В первом случае вершины из Т, имеющие тип Т индуцируют треугольный подграф Т(5), а во втором случае каждая вершина из Т — {х} имеет тип Т. Покажем, что первый случай невозможен. В противном случае для вершины у типа Г из Т подграф А(у) является объединением двух непересекающихся 2x4 решеток. Без ограничения общности, можно считать, что первая решетка содержит клики {аг, ...,04}, {61,...,64}) а вторая решетка содержит клики {с2,...,с5}, {d2,--,d5}, причем вершины, имеющие заданный индекс, образуют клику. Ребра {ai,bi}, {5, 5} назовем концевыми. Теперь 5-клика графа А(у), состоящая из вершин типа Е, содержит концевое ребро и 3 вершины /i,/2,/3, отвечающие четырехугольникам 2 х 4-решетки, содержащим указанное концевое ребро. Если вершины 7ъ 72, 7з отвечают четырехугольникам второй 2 х 4-решетки из Д(у), содержащим другое концевое ребро, то {/х,..., /з, pi,..., #з} является октаэдром. Противоречие с тем, что Д(/г) содержится в Т. Утверждение (2) доказано. Допустим, что каждая вершина из Т имеет тип Е. Тогда Т является связной компонентой графа А. Так как в «7(10, 5) нет вершин, изолированных от подграфа Г(б), то А = Т. Лемма 2.56 Выполняются следующие утверждения: 1. Для любой вершины х Є Г2(а) найдется такая б -клика L — Lx в Гз(о) П [х], что для d Є L вершина х имеет тип в графе Г2(а) Г) [d], а для любой вершины є Є Г3(а) П [х] — L вершина х имеет тип Т в графе Г2(а)п[е]. 2. Клика L является объединением двух треугольников Lh,Lv, таких что Г2(а) П [х] содержит две изолированные 3x4 решетки Фд, Ф„, причем Г2(а) П [ж] П [d] С Фж, если d Є Lx. 3. .Бели некоторая вершина смежна с З вершинами грани октаэдра [а] П [х], то будем говорить, что она лежит на этой грани. Грани октаэдра [а] П [х] разобьем на два класса, в один из которых соберем грани, которые попарно пересекаются точно по вершине (раскрасим грани в шахматном порядке). Тогда вершины решетки Фд лежат на гранях одного цвета (по 3 вершины па грани), а вершины решетки Ф„ лежат на гранях другого цвета. Доказательство. Пусть х Є Г2(а). Тогда ІІГо(М П [ж]) = [х] П Г3(а). Зафиксируем вершину b Є [а] П [х] и представим [х] как объединение {6} U ([Ь] П [ж]) с множеством вершин, отвечающих четырехугольникам решетки [Ь] П [х]. Тогда октаэдр [а] П [х] содержит Ь, четырехугольник Ф из [Ь] П [х] и вершину, отвечающую Ф. Тогда / о([а] П [х]) состоит из вершин, отвечающих четырехугольникам, не пересекающим Ф. По лемме 2.54 вершина х имеет тип Е в графе Г2(а)П[ і] тогда и только тогда, когда четырехугольник, отвечающий d, не пересекает Ф и имеет две общих прямых с Ф, вершина х имеет тип Т в графе Г2(а) П [е] тогда и только тогда, когда четырехугольник, отвечающий е, не пересекает Ф и имеет единственную общую прямую с Ф.
Вершины, отвечающие четырехугольникам, не пересекащим Ф и имеющим две общие горизонтальные (вертикальные) прямые с Ф, образуют 3-клику, которую назовем горизонтальной (вертикальной). Так как четырехугольники, отвечающие вершинам горизонтальной и вертикальной клик изолированы в решетке [й]п[ж], то каждая вершина горизонтальной клики смежна с каждой вершиной вертикальной клики. Утверждение (1) доказано.
Если {di, d2, d3} — горизонтальная 3-клика из L, то подграфы Г2(а) П [х] П [di] являются 2x4 решетками, попарно пересекающимися по разным 4-кликам. Таким образом, объединение трех указанных решеток является 3 х 4 решеткой Фд из Г2(а) П [х]. Симметрично, вертикальной 3-клике из L отвечает 3x4 решетка Ф„, причем решетки Ф/і и Ф„ изолированы. Утверждение (2) доказано.
Грани октаэдра [а] П [х] можно разбить на два класса, в один из которых соберем грани, которые попарно не пересекаются по ребру (раскрасим грани в шахматном порядке). Если некоторая вершина смежна с 3 вершинами грани октаэдра, то будем говорить, что она лежит на этой грани. Если х — вершина типа Е в графе Г2(а) П [d], то, без ограничения общности, решетке Ф/j отвечают белые грани, причем на каждой белой грани лежат по три вершины решетки, а решетке Ф„ отвечают черные грани. Утверждение (3) доказано.
