Содержание к диссертации
Введение.
Глава 1. Регулярные графы с малыми значениями Ъ\. 1.1. Вспомогательные результаты.
1.2. Почти хорошие тройки в реберно регулярных графах. 1.3. Сильно регулярные графы с Ь\ < 18. 1.4. Вполне регулярные графы с Ъ\ < 5.
Глава 2. Узкие частичные четырехугольники и их автоморфизмы.
2.1. Параметры узких частичных четырехугольников.
2.2. Автоморфизмы сильно регулярного графа с (400,21,2,1).
Глава 3. Однородные расширения частичных геометрий.
3.1. О s-однородных расширениях геометрий pGa(s, t).
3.2. Сильно (s—1)-однородные расширения геометрийpGQ(s, t).
Литература
Введение к работе
Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ь — вершины графа Г, то через d(a, b) обозначим расстояние между а и 6, а через Г; (а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии і от вершины а. Подграф Гі (а) будем называть окрестностью вершины а и обозначать через [о]. Через а1 обозначим подграф, индуцированный {a} U [а].
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Число вершин в [а] Г) [Ь] обозначим через \(a,b) (fi(a,b)), если d(a,b) = 1 (d(a,b) = 2), а соответствующий подграф назовем (//-) Л-подграфом. Граф Г назовем реберно регулярным с параметрами (v,k:X), если он содержит v вершин, регулярен степени к, и каждое его ребро ab лежит в Л треугольниках. Граф Г — вполне регулярный граф с параметрами (г;, к, А, /г), если он реберно регулярен с соответствующими параметрами и [а] П [6] содержит /і вершин для любых двух вершин а, Ъ, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Через i^miv..)jrin обозначим полный n-дольный граф, с долями порядков mi, ..., тп. Если mi = ... = тп = т, то соответствующий граф обозначается через Кпхт. Треугольным графом Т(т) называется граф с множеством неупорядоченных пар из X в качестве вершин, \Х\ = т и пары {a,b},{c,d} смежны тогда и только тогда, когда они имеют общий элемент. Граф на множестве вершин X х Y называется т х п решеткой, если \Х\ = т, \Y\ = п и вершины (a?i,yi), (х2,У2) смежны тогда и только тогда, когда х\ = Х2 или yi = у2-
Графом Джонсона J(n,m) называется граф, вершинами которого являются m-элементные подмножества данного n-элементного множества, причем две вершины а, Ь смежны, только если \а П b\ = m — 1. Граф Пэ-ли P(q) в качестве вершин имеет элементы поля Fq, q = 1 (mod 4), и две вершины а, Ь смежны, только если Ъ — а является ненулевым квадратом в Fq. Граф Петерсена — это дополнительный граф для треугольного графа Т(5) (он имеет параметры (10,3,0,1)). Граф Клебша (Шлефли) — это единственный сильно регулярный граф с параметрами (16,10,6,6) (с параметрами (27,16,10,8)). Граф Шрикханде — это единственный сильно регулярный локально шестиугольный граф с параметрами (16,6,2,2). Имеется точно 3 сильно регулярных графа, имеющих параметры графа Т(8), но не изоморфных Г(8). Эти графы называются графами Чанга. Графом Хофмана-Синглтона называется единственный сильно регулярный граф с параметрами (50,7,0,1). Графом Хигмена-Симса называется единственный сильно регулярный граф с параметрами (100,22,0,6).
Частичной геометрией pGa(s, і) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Если a = t, то геометрия называется сетью. Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Легко понять, что точечный граф частичной геометрии pGa(s,t) сильно регулярен с параметрами v = (s+l)(l + st/a), k = s(t+l), A = (s — 1) + (а — l)t, ji = a(t +1). Любой сильно регулярный граф с таки-
ми параметрами для некоторых a, s, t называется псевдогеометрическим графом для pGa(s,i).
Множество вершин графа MZ(n), отвечающего аффинной плоскости 7г = (X, С) порядка п, совпадает с X U С, причем подграф X является кокликой, точка смежна с прямой, только если она принадлежит этой прямой и две прямые смежны, если они не пересекаются. Граф MZ(n) имеет п(2п + 1) вершин, является кореберно регулярным с [і = 1, причем А (а, Ь) = О, если одна из этих вершин — точка, а другая — содержащая эту точку прямая, А(а, Ь) = п — 2, если а и Ъ — параллельные прямые.
Частичным четырехугольником PQ(s, t: ц) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любых двух несмежных точек пересечение их окрестностей в точечном графе является //-кокликой. Точечный граф частичного четырехугольника PQ(s, t, ц) сильно регулярен с параметрами v = 1 + s(t + 1) + sH(t + 1)/ц, k = s(t + 1) и \ = s — 1. Частичный четырехугольник назовем узким, если t < 6.
Граф Г диаметра d называется дистанционно транзитивным, если для любого і Є {0, ...,d} и для любых вершин u,v,x,y с условиями d(u,v) = d(x, у) = і, существует автоморфизм g графа Г такой, что (и9, vg) = (х, у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Более половины спорадических групп имеют представления в виде групп автоморфизмов графов ранга 3 [39].
Если вершины и, w находятся на расстоянии і в Г, то через b{(u, w) (через Ci(u,w)) обозначим число вершин в пересечении Гі+і(и) (в пересечении Ті-і(и)) с [w]. Дистанционно регулярным графом называется граф диа-
метра d, в котором для любого і Є {0,1,..., d} параметры b{(u, w) и Cj(w, w) не зависят от выбора вершин и, w, а зависят только от расстояния между этими вершинами в графе Г.
Заметим, что в реберно регулярном графе с параметрами (v, к, А) значение &i(u, w) не зависит от выбора ребра {и, w} и равно к — А — 1.
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [24-25]. Например, класс билдингов Титса характеризует группы лиевско-го типа [42]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [21].
Пусть G — транзитивная группа подстановок на множестве О,. Если подгруппа Gp группы G, состоящая из всех подстановок, фиксирующих точку абП, имеет г орбит, то говорят, что G является группой ранга г. Пусть г = 3 и соответствующие 3 орбиты — это {а},Г(а), А(а). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого -Пи две вершины р, q смежны в Г, если р Є T(q) [ЗО].
Д.Хигмен [30-34] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, т. е. дистанционно транзитивных графов диаметра 2.
Ярким примером перехода от изучения групповых симметрии к комбинаторным является расширение класса дистанционно транзитивных графов до класса дистанционно регулярных графов. В настоящее время при
исследовании графов и конечных геометрий вовлекаются симметрии все более общего вида.
Поскольку каждый дистанционно регулярный граф является вполне регулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов.
В диссертации получено описание вполне регулярных графов с Ь\ < 5 и найдены параметры сильно регулярных графов с Ь\ < 18; изучены узкие частичные четырехугольники и доказано, что сильно регулярный граф с параметрами (400,21,2,1) не является вершинно транзитивным; классифицированы s-однородные и сильно (s — 1)-однородные расширения частичных геометрий pGa(s, і).
Результаты работы докладывались на Международной алгебраической конференции, посвященной 70-летию Л.Н. Шеврина (Екатеринбург, 2005), на Международных конференциях "Мальцевские чтения" (Новосибирск, 2005 и 2006), на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения А.И. Старостина (Приэльбрусье, 2006), на 37-й и 38-й Региональных молодежных конференциях ИММ УрО РАН, на алгебраических семинарах Института математики и механики УрО РАН.
Основные результаты опубликованы в работах [13-19]. Работы [13-18] были написаны в нераздельном соавторстве с Махневым А.А.
Диссертация состоит из введения, трех глав и списка литературы (43 наименования). Ссылка на теорему i.j означает, что она находится под номером j в главе і. Ссылка на утверждение i.j.к означает, что оно находится под номером к в параграфе j главы і.
В главе 1 рассматриваются графы с малыми значениями Ь\. Пусть Г —
реберно регулярный граф с параметрами (v, к, А). Тогда степень вершины в любом //-подграфе из Г не больше k—2bi. Поэтому для //* = к—2&1+1 и любых вершин и, w, находящихся на расстоянии 2, выполняется неравенство fi(u,w) > /і*. Пару вершин (u,w), находящихся на расстоянии 2, назовем хорошей, если /і(и, w) = /z*; назовем почти хорошей, если fi(u, w) = /z* +1. Для w, z Є ^(w) тройку вершин назовем хорошей, если /z(u, w) + fi(u, z) < 2k — 4&i + 3; назовем почти хорошей, если /л(и, w) + у>{и, z) = 2к — 46i + 4.
Первые результаты о хороших парах получены в [4], где, в частности, установлено, что пересечение окрестностей вершин хорошей тройки содержит не более одной вершины.
При изучении реберно регулярных графов полезным является описание почти хороших троек. Следующий результат особенно полезен при изучении графов диаметра, большего 2.
Теорема 1.1. Пусть Г — связный реберно регулярный граф с параметрами (v,k,X); &i = к — Л — 1 и к > 3&1 — 3. Если тройка (u;w,z) является почти хорошей и [w] П [z] — [и] содержит вершину у, несмежную с вершинами из А = [и] П [w] П [z], то либо |А| < 2, либо |Д| = 3 и (6^)6((5,12),(6,15),(6,17).
Замечание. Если Г — граф Шлефли, d(u, w) = 2, то /і = k—2&і+2, [и]П [w] является полным миогодольным графом Кіх2 и для любой вершины Z Є [w] — [и] подграф [и] П [ги] П [z] является 4-кликой. Но в этом графе каждая вершина из [w] П [z] — [и] смежна с некоторой вершиной из [и] ҐІ [w] П [z].
Изучение реберно регулярных графов даже в случае Ь\ = 5 идет с большим трудом. Однако для сильно регулярных графов ситуация гораздо проще.
Сильно регулярные графы с собственным значением —2 были класси-
фицированы Зейделем [40]. Любой зейделев граф — это либо полный многодольный граф КГХ2, либо решетчатый или треугольный граф, либо один из графов Шрикханде, Чанга, Петерсена, Клебша или Шлефли.
Теорема 1.2. Пусть Г — сильно регулярный граф с 0 < Ь\ < 18. Тогда Г является одним из следующих графов:
граф с параметрами (4Ь\ + 1,2&і,&і — 1,Ьі), Ь\ ф 5,8,14,17 или полный многодольный граф Кгхф1+і);
зейделев граф или его дополнение;
псевдогеометрический граф для GQ(s, t), {s, t} = {2,2}, {2,4}, {3,3}, {3,5} или его дополнение;
псевдогеометрический граф для сети pGt{s,t), где либо t = 2,s = 4,5,6,7,8 или 9, либо t = 3, s = 4,5,6 или 7;
псевдогеометрический граф длярЄ^(5,2), pGz(6,2), pG±{l, 2), р(?з(8,2), PG3(9,2), PG4(7,S), pG4(M), pG5(9,3), pG6(8,5), P<38(15,2); pGi2(16,3), pGi5(19,3) MupG20(24,3);
дополнительный граф либо к графу из пунктов (4) или (5), либо к псевдогеометрическому графу для рб?2(4,7) или pG^(b, 7);
граф с параметрами (49,32,21,20), (50,7,0,1), (56,10,0,2), (77,16,0,4), (85,14,3,2), (99,14,1,2), пли (126,25,8,4);
дополнительный граф либо для графа из пункта (7), либо для графа с параметрами (81,20,1,6) или (100,22,0,6).
Хорошо известно, что связный граф с Ъ\ = 1 является многоугольником или полным многодольным графом с долями порядка 2. Графы сЬ\ Є {2,3} изучались в [10], графы с Ь\ = 5 и к > 14 классифицированы в [7], а вполне регулярные графы с Ь\ = 4 описаны в [3].
Теорема 1.3. Пусть Г — связный вполне регулярный граф с парамет-
рами (v, к, А,д) и Ъ\ < 5. Тогда ли^о Г является полным многодольным графом Jfnx(61+i), регулярным графом без треугольников степени Ь\ + 1 w^w реберным графом регулярного графа без треугольников степени Ь\ +1 обхвата, большего 1, либо выполняется одно из следующих утверждений:
Ь\ = 2 и Г является 3 х 3-решеткой, треугольным графом Т(5), графом Петерсеиа или графом икосаэдра;
&i = 3 и Г является локально шестиугольным графом, треугольным графом Т(6) или графом Клебша;
Ъ\ = 4 и либо
(г) диаметр Г равен 2 и Г является графом Пэли с параметрами (17,8,3,4), 5x5 решеткой, треугольным графом Г(7) мли дополнительным графом к 4 х 4 решетке, треугольному графу Г(6) или графу Клебша,
(и) [і = 1 и Г является вполне регулярным графом с параметрами (t/,6,1,1),
(ш) /х = 2 и Г является либо графом Клейна, либо Ъ-кубом, либо графом инцидентности симметричной 2-(11,5,2) схемы, либо единственным вполне регулярным графом с параметрами (20,6,1,2),
(iv) /і = 4 и Г является графом Джонсона J(6,3); (5) Ь\ = 5 и либо
(г) диаметр Г равен 2 и Г является 6x6 решеткой, графом Шлефли, треугольным графом Т(8) или одним из трех графов Чанга,
(И) /і = 2 и Г является либо 6-валентным ректаграфом, либо локально восьмиугольным графом диаметра, не большего 4.
Пример 1. Пусть Г — граф, вершинами которого являются 3-циклы из симметрической группы .%, причем две вершины а, Ь смежны, если аЬ является инволюцией. Тогда Г является вполне регулярным графом с параметрами (20,6,1,2).
Во второй главе работы классифицированы узкие частичные четырехугольники и изучены их автоморфизмы.
Легко понять, что граф коллинеарности частичного четырехугольника PQ(s,t,ii) сильно регулярен с параметрами (l + s(t + l) + s2t(t + l)/fi, s(t + l),s — 1,/і). Обратно, если сильно регулярный граф не содержит индуцированных подграфов, изоморфных К± с удаленным ребром, то система инцидентности, точками которой являются вершины графа, а прямыми — максимальные клики графа, будет частичным четырехугольником.
Ясно, что сильно регулярный граф с А < 1 или с \i = 1 является графом коллинеарности частичного четырехугольника. Назовем частичный четырехугольник PQ(s,t,fj,) узким, если t < 6.
Теорема 2.1. Пусть Г является графом коллинеарности частичного четырехугольника PQ(s,t,/j), t < 6. Тогда выполняется одно из следующих утвероісдений:
Г — полный двудольный граф Кщп или п х п решетка;
Г — граф коллинеарности GQ(s,t), 2 < t < 6;
Г — граф Петерсена, граф Хофмана-Синглтона, дополнительный граф для графа Клебша, граф с параметрами (99,14,1,2) или (400,21,2,1).
Группа автоморфизмов полного двудольного графа Кщп и п х п решетки является сплетением Sn с помощью группы порядка 2. Группа автоморфизмов графа Петерсена изоморфна 5*5, графа Хофмана-Синглтона — расширению группы С/з(5) с помощью группы порядка 2 и дополнительного графа для графа Клебша — расширению элементарной группы порядка 16 с помощью группы а%. Строение группы автоморфизмов гипотетического графа с параметрами (99,14,1,2) выяснено в [12].
Теорема 2.2. Пусть Г является сильно регулярным графом с параметрами (400,21,2,1), д — элемент простого порядка р из Aut(r) и A = Fix(g). Тогда выполняется одно из следующих утверждений:
А — пустой граф и р = Б;
либо |А| = 1 и р = 3 или 7, либо А является 4-кликой и р = 2 или
3;
(3) р = 2, А содержится в а1 для некоторой вершины а Є А, А (а) яв
ляется объединением <р изолированных вершин и ф треугольников, при-
чем (<р,ф) = (0,7), (3,4), (2,3), (1,2), (6,1) или (5,0).
В доказательстве теоремы 2.2 используется метод Г. Хигмена приложения теории характеров конечных групп к изучению возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов (см. [27]).
Следствие. Пусть Г является сильно регулярным графом с параметрами (400,21,2,1) и G = Aut(r). Тогда выполняется одно из следующих утверждений:
7 делит \G\ и \G\ делит 2-3-7;
5 делит \G\ и \G\ делит 10 или 3 52;
\G\ делит 2 З3.
В третьей главе диссертации изучены (^-однородные расширения частичных геометрий pGa(s,t) с ip = s и сильно (^-однородные геометрии с <р = s — 1. В частности, полученные ранее Камероном и Фишером [28] результаты по расширениям обобщенных четырехугольников обобщаются на случай частичных геометрий.
Геометрией S ранга 2 называется система инцидентности (Р,В), где Р — множество точек, В — некоторый набор подмножеств из Р, называемых
блоками. Две точки называются коллинеарными, если они лежат в общем блоке. Пара (а, В) из (Р, В) называется флагом, если точка а принадлежит блоку В, и антифлагом в противном случае. Геометрия называется (^-однородной, если для любого антифлага (а, В) число точек в блоке В, коллинеарных точке а, равно 0 или <р, и сильно (^-однородной, если это число всегда равно
Вычет Sa геометрии S в точке а — это геометрия (Ра,Ва), где Ра — множество всех точек, коллинеарных аиВа = {В—{а} | а Є В Є В}. Пусть Т - семейство геометрий ранга 2, и всякий вычет Sa лежит в Т. Тогда говорят, что «5 является расширением Т. Связное расширение семейства частичных геометрий pGa(s,t) обозначается как EpGa(s,t).
Пусть геометрия S является ^-однородной EpGa(s,t). Если (f = s + 2, то «S называется одноточечным расширением (и граф Г(е>) является полным). Например, 3-(22,6,1) схема Матье — это одноточечное расширение проективной плоскости Р(7(2,4).
Если (р = s + 1, то геометрия S будет сильно (s + 1)-однородной, и Г является полным многодольным графом K(s+2)x(i+st/a)- В этом случае для любой точки а множество точек вычета Sa имеет разбиение на s + 1 ово-идов. Среди известных обобщенных четырехугольников только GQ(s, 1), GQ(l,t),GQ(2a,2a),GQ(q2,q),GQ(q-l,q+l),GQ(q + l,q-l),rzeq-степень простого числа, допускают разбиение точечного множества овои-дами.
Пример 2. Для любого t > 1 имеется единственная геометрия EGQ(1, і). Ее точечный граф является полным трехдольным графом .Кзх(ш)) а мн0~ жество блоков совпадает с множеством 3-клик этого графа.
Пример 3. Сильно (s + 1)-однородный четырехугольник EGQ(s, 1) су-
ществует при всех s = q — 1, где q есть степень 2. Примеры cs = 1hs = 3 единственны [29].
Пусть 7г = PG(2,q), а — точка в 7Г, С - гиперовал, содержащий a, a Т обозначает группу (порядка q2) всех элаций с центром в точке а. Точками EGQ являются все точки 7Г, отличные от а; блоками являются прямые, не содержащие а, и трансляции прямой С — {Р} под действием группы Т.
Примеры (s + 1)-однородных EGQ(q — l,q + 1) для g = 2п построены А. Пасини и Д. Пасечником.
Теорема 3.1. Пусть S является s-однородной геометрией EpGa(s,t), а Г - дополнение к T(S). Тогда либо s = 2 (и геометрия S известна), либо S есть EpG2(s, 1), Г является сильно регулярным графом с X = 0, ц = 2, и S есть геометрия вершин и клик графа Г, соответствующих Г (а) для а Є Г; либо S сильно s-однородна и одно из следующих утверждений верно:
t = а и Г есть граф, являющийся квадратной решеткой на (s + 2)2 вершинах;
t = 2ol, s < (2а - 1)(а + I)2, s + а + 1 делит 2s(s + 1)(2а + 1), и Г есть треугольный граф на (s + 2) (2s + 3) вершинах.
Пример 4. Сильно s-однородная геометрия EGQ(s, 1) существует для всех s = q — 2, где q есть степень двойки [29].
Пусть 7Г = PG(2,q), а и Ъ являются точками 7г, L есть прямая ab, С -гиперовал, содержащий а и 6, а Г — это группа всех центральных коллине-аций с центром а и осью, содержащей Ь. Тогда \Т\ = q(q — 1), Т фиксирует все прямые, проходящие через а и является точно 2-транзитивной группой на множестве прямых, проходящих через Ь и отличных от L.
Множество точек геометрии EGQ(s, 1) состоит из точек 7Г, которые не
лежат на L, а множество блоков является объединением множества прямых 7Г, не содержащих а или 6, и образов С — {Р, Q} под действием группы элаций Т.
Пример 5. Сильно 3-однородная геометрия EpGi{?>, 2) существует.
Пусть точечное множество S есть множество позиций ij квадратной матрицы порядка 5, а множество блоков В задано наборами {Іг'і, 2г*2,..., бг^}, такими, что перестановка (І1І2—І5) имеет знак плюс.
Ясно, что \В\ = 5!/2 = (f+ l)(s + l)(s + 2) для t = 2, s = 3 и /(а, Я) = 3 для любого антифлага (а, Б).
Далее, для точки a = хіх имеем \Ра\ = 16, \Ва\ = 16, каждая точка из Ра принадлежит трем блокам из Ва и каждый блок из Ва содержит 4 точки из Ра. Таким образом, (Р, В) является сильно 3-однородной геометрией EpG2{3,2).
Теорема 3.2. Пусть S является сильно (s — 1)-однородной геометрией EpGa(s,t). Тогда либо S является геометрией EpG2X{^x,3x — 1) для некоторого нечетного х, либо S = EGQ(3,1), EGQ(S,9), .Ер(?2(6,15), EpG2{7,6) шшрз(7,9).
Дж. Тас построил частичную геометрию рС?2Х(3:с,3 — 1) с х = 32п~2, с помощью спреда гиперболической квадрики в проективном пространстве PG(4n — 1,3) [41]. К настоящему времени известно существование такого спреда только для случая п = 2.
Автор выражает глубокую признательность научному руководителю чл.-корр. РАН Махневу А.А. за постановку задач и постоянное внимание.
