Расширения обобщенных четырехугольников и их автоморфизмы тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Хамгокова, Мадина Мухадиновна

• Хамгокова, Мадина Мухадиновна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Хамгокова, Мадина Мухадиновна

ОГЛАВЛЕНИЕ

Введение

Глава 1. Предварительные сведения

Глава 2. Расширения обобщенных четырехугольников

§ 2.1. Локально 4)-графы

§ 2.2. Внолне регулярные локально С<5(4, 6)-графы

Глава 3. Расширения обобщенных четырехугольников С(5(5, 3)

§ 3.1. Вполне регулярные локально 3)-графы

§ 3.2. Дистанционно регулярные локально псевдо С<5(5, 3)-графы

Глава 4. Автоморфизмы расширений обобщенных четырехугольников

§ 4.1. Автоморфизмы сильно регулярнго графа с параметрами (322,96,20,32)

§ 4.2. Автоморфизмы сильно регулярнго графа с параметрами (322, 96, 20, 32), в котором окрестности вершин — точечные графы для <73(5, 3)

Литература

Введение диссертации (часть автореферата) на тему «Расширения обобщенных четырехугольников и их автоморфизмы»

Введение

Актуальность темы исследования. Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию. Например, класс билдингов Титса характеризует группы лиева типа [11]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [3].

Пусть Ь(Кп) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т{п). Этот граф является сильно регулярным графом с параметрами (п(п — 1)/2, 2(п — 2), п — 2,4).

Реберный граф Ь(Кт1П) полного многодольного графа Кт<а является ко-реберно регулярным графом с параметрами (гап, т + п — 2, 2). Граф Ь(Кт>п) называют т х п-решеткой. При т = п решетчатый граф является сильно регулярным графом с параметрами (п2, 2п — 2, п — 2, 2).

Дж. Зейдель [10] классифицировал все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение равно —2, являются только полные многодольные графы Кпх2, графы Пстерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через с/(а, Ь) обозначается расстояние между а и 6, а через Гг(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.

Подграф Г^а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.

Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.

Граф Г называется реберно регулярным графом с параметрами (у,к,Х), если Г содержит V вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.

Граф Г называется вполне регулярным графом с параметрами (и, к, А, /¿), если Г реберно регулярен с соответствующими параметрами и подграф [а]П [&] содержит р, вершин в случае ¿(а, Ъ) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.

Число вершин в [а] П [Ь] обозначим через Х(а,Ь), если с£(а, Ь) — 1, а соответствующий подграф назовем Х-подграфом.

Если с?(а, 6) = 2, то число вершин в [а] П [6] обозначим через д(а, Ь), а соответствующий подграф назовем ¡л-подграфом.

Если вершины и, ио находятся на расстоянии г в Г, то через ЬДи, и;) (через Сг(и, ги)) обозначим число вершин в пересечении Г¿+1(14)

(Г^^)) с Заметим, что в реберно регулярном графе число Ь\(и,и]) не

зависит от выбора смежных вершин и. и] и равно Ь\ — к — X — 1.

Граф Г диаметра с? называется дистанционно регулярным с массивом пересечений {60, &1,..., ь сх,..., с^}, если значения Ь{(и, ги) и и>) не зависят от выбора вершин и, ги на расстоянии г в Г для любого г — 0,с?.

Пусть Т — некоторый класс графов. Граф Г назовем локально Т-графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу Д, то граф Г назовем

локально А-графом.

Задача описания локально (3(2(5, ¿)-графов (графов, в которых окрестности вершин являются точечными графами для является классической и решена для в < 3 (см. [2,5,15-17]). При изучении локально С(3(4Л)-графов найдены вполне регулярные графы для значений Ь £ {1,2,8,11,12,16} [13,19,29,31,34]. Изучение вполне регулярных локально С<5(5, £)-графов только начато. Получена классификация для Ь = 5 [26].

Цель диссертации. Изучить расширения некоторых обобщенных четырехугольников и найти автоморфизмы сильно регулярного графа с параметрами (322,96,20,32), возникшего при изучении локально С<5(5, 3)-графов.

Методы исследования. Основными методами исследования являются теоретико-графовые методы и методы теории конечных групп, в частности метод Хигмена приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов.

Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие:

- доказано несуществование вполне регулярных локально С(5(4,4)-графов,

- получено описание вполне регулярных локально (?<5(4, 6)-графов,

- получено описание вполне регулярных локально С(5(5, 3)-графов,

- найдены возможные автоморфизмы и подграфы их неподвижных точек для сильно регулярного графа с параметрами (322,96,20,32),

- классифицированы дистанционно регулярные локально псевдо £(3(5,3)-графы.

Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение расширений обобщенных

четырехугольников и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных геометрий подобного типа.

Апробация работы. Основные результаты работы докладывались на следующих конференциях: "Перспектива Международная конференция студентов, аспирантов и молодых ученых (2009 г., Нальчик); VIII Международная школа-конференция по теории групп (2010 г. Нальчик); 43 Международная молодежная школа-конференция "Современные проблемы математики" (2012 г. Екатеринбург), Международная конференция "Алгебра и комбинаторика посвященная 60-летию A.A. Махнева (2013 г., Екатеринбург), X Международная школа-конф. по теории групп, посвященная 70-летию В.В. Кабанова (2014 г., Нальчик).

Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН и Кабардино-Балкарского госуниверситета.

Публикации. По теме диссертации имеется 10 публикаций [23-25,27-28,30, 32-33,35-36] (четыре статьи опубликованы в журналах из списка ВАК). Из пяти статей одна написана без соавторов, четыре - тремя авторами (Мах-нев A.A., Падучих Д.В., Хамгокова М.М.). Все совместные работы написаны в нераздельном соавторстве.

Структура и объем работы. Работа состоит из введения, четырех глав и списка цитированной литературы, содержащего 36 наименований. Объем диссертации — 73 стр.

В главе 1 приведены предварительные сведения. В главе 2 доказано несуществование вполне регулярных локально GQ(A, 4)-графов и классифицированы вполне регулярные локально GQ(4, 6)-графы. В главе 3 изучены вполне регулярные локально GQ(5,3)-графы и классифицированы дистанционно ре-

гулярные локально псевдо 3)-графы. В главе 4 найдены автоморфизмы

сильно регулярного графа с параметрами (322,96,20,32).

Глава 1. Предварительные сведения

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ь — вершины графа Г, то через с1(а, Ь) обозначается расстояние между а и Ь, а через Гг-(а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии г от вершины а. Подграф Гх(а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а. Для подмножества X вершин графа Г через X1- обозначается П^ехх-"1.

Регулярным графолг степени к называется граф Г, такой что для любой вершины и е Г выполняется |Г(г^)| = к. Реберно регулярным графом с параметрами (и, к, Л) называется регулярный граф степени к на V вершинах, любое ребро которого лежит точно в Л треугольниках. Вполне регулярным графом с параметрами (у, А;, Л, ц) называется реберно регулярный граф с параметрами (г>, /с, Л), в котором любые две вершины и, ги е Г на расстоянии 2 имеют ровно ¡1 общих соседей. Сильно регулярным графом с параметрами (у,к,\,(1) называется реберно регулярный граф с параметрами (г», к, А), в котором любые две несмежные вершины и, и) £ Г имеют ровно ¡1 общих соседей.

Заметим, что сильно регулярный граф с д > О является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с с? > 2 — вполне регулярным графом с к — Ь0, А = к — Ъ\ —1 и /л — с2.

Пусть задан класс графов Т'. Мы скажем, что граф Г является локально Т-графом, если для любой вершины а € Г имеем Г(а) Е Т. Можно поставить задачу описания локально ^-"-графов. Если граф Г вершинно симметричен, то окрестности всех его вершин изоморфны, и граф Г является локально Т-графом, где Т состоит из графов, изоморфных некоторому графу А. В этом

случае назовем Г локально А-графом. В более общем случае Т может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных, реберно регулярных графов — это в точности класс связных, локально регулярных графов.

Для подграфа А пусть .Xj(A) — множество всех вершин из Г —А, смежных точно с г вершинами из А, гсДА) = |Xj(A)|.

Определим несколько сильно регулярных графов, которые будут фигурировать в диссертации, а также являются примерами локально А-графов.

Через Kmi,...,m„ обозначим полный п-дольный граф, с долями порядков mi, ...,mn. Если mi = ... = mn = m, то соответствующий граф обозначается через Кпхт (и является локально /^(п_1)хт-графом). Граф К\ т называется т-лапой. Графом Тэйлора называется дистанционно регулярный граф с массивом пересечений {к, 1; 1, д, /с}.

Пусть М и N—конечные множества порядков тип, соответственно. Два элемента из М х N будем считать смежными, если они различаются точно в одной координате. Полученный граф называется тхп-решегпкой; при т = п он сильно регулярен с параметрами (п2, 2(п — 1), п — 2, 2).

Треугольным графом Tin) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда, когда они пересекаются в точности по одной точке. Граф Т(п) сильно регулярен и имеет параметры (п(п — 1)/2,2(п — 2),п — 2,4). Окрестность каждой вершины в Т(п) изоморфна 2 х (п —2)-решетке, т.е. Т(п) — локально 2 х (п — 2)-решетка. Верно и обратное: связный локально 2 х (п — 2)-граф изоморфен Т(п).

Приведем некоторые результаты о локально ^"-графах.

Лемма 1.1. Пусть Г — локально GQ(s,t)-zpa4). Тогда максимальные клики из Г состоят из s + 2 точек (такие клики мы будем называть бло-

ками), каждая точка лежит в (£ + 1)(в£ + 1) блоках, любые две смежные точки лежат в £ +1 общих блоках, любые два блока пересекаются не более чем по двум точкам.

Доказательство. Все утверждения следуют из определения локально графа и свойств 5 (см. [7]).

Лемма 1.2. Пусть А — гиперовал в обобщенном четырехугольнике

¡1 = |А|. Тогда /л четно, и выполняются следующие утверэ/сдения:

(1) < ^ < /Л где /1* = тах{2{1 + 1), (в + + 2 - в)}, /л* = 2^ + 1);

(2) если ¡1 = (в + 1)(£ + 2 — з) (ц = ¡1*), то для любой точки а ^ А точно (£ + 2 — 5)/2 прямых (все прямые) из а1 пересекают А по двум точкам;

(3) ¡IXо <{У-1Х)(У- х0)(г + 5)2/(2в(* + 1) + * + 2 - Й)2.

Доказательство. Оценки для ¡л и четность ¡л следуют из лемм 3.9, 3.11 [7]. Если ¡л = (з + 1)(£ + 2 — 5), то из доказательства леммы 3.11 [7] следует, что для а ^ А число прямых из сг1, не пересекающих Л, равно (в + £)/2.

Если /л = /л*, то по лемме 3.9 (Ь) из [7] каждая прямая пересекает Л (естественно по двум точкам).

Так как между Л и Хо нет ребер, то по предложению 4.6.1 из [4] имеем

(лх0 <{у-^){у- яо)(01 - ^)7(2к - 01 - в2)2, где в2 = -(* + 1), в1 = з - 1 -

неглавные собственные значения графа Г. Поэтому /лхо < (у — ¡л)(у — +

Лемма 1.3. Если Г является сильно регулярным графом с параметрами (у, к, А, /х) и неглавными собственными значениями п — т, —т, то

(1) к(к — А — 1) = ¡л{у — к — 1) (прямоугольное соотношение);

(2) кратности отличных от к собственных значений г > 0 и I < 0 равны

5)7(25(^+1) +¿ + 2 -б-)2.

-к(1 + 1)(к-1) (,к + г1)(г-1)

к(г+1)(к-г) (к + г1){г — I)

(требование, что данные дроби должны быть натуральными числами, называется условием целочисленности);

(3) либо Г имеет параметры (4// + 1,2/1, д — 1,/л) (половинный случай), либо (А —¡л)2-\-4[к—ц) — п2 для подходящего натурального числа п (п — г — 1) и собственные значения г и I целые.

Доказательство. Все утверждения леммы хорошо известны и могут быть найдены, например в [3, глава 1].

Лемма 1.4. Пусть Г - сильно регулярный граф, имеющий параметры (у, к, А, р,), А - индуцированный подграф) с N вершинами, М ребрами и степенями вершин ,..., ¿¿дг. Тогда

Ейо а*

гхг = кЫ - 2М,

Доказательство. Указанные равенства следуют из подсчета числа вершин в Г — А, числа ребер между А и Г — А и числа 2-путей с концами в А и средней вершиной в Г — А. Лемма доказана.

Лемма 1.5. Пусть Г — дистанционно регулярный граф с массивом пересечений {Ьо, С\,..., с^}. Тогда выполняются следующие утверждения:

(1) ц делит Мг+ъ сгсг+1 и а2{а2 - а1) + Ь2с3 - к;

(2) с2 делит ^(сц + ат - аг) и <^+1(0* + ат - а{);

(3) если неглавное собственное значение в^ имеет кратность меньшую к, то г Е {1,<^} и для Ь = Ъ\/{вг + 1) каждая окрестность вершины в графе Г имеет собственное значение —1 — 6 кратности, не меньшей к —

Доказательство. Утверждения (1-2) следуют из леммы 4.1.7 [3] (напри-

мер, утверждение (1) следует из целочисленности ъ Р2г+1 и Рм)-

Утверждение (3) следует из теоремы 4.4.4 [3].

Лемма 1.6 (см. [4, §3.15, упражнение 3]). Пусть Г является сильно регулярным графом с параметрами (и, к, А, /г) и неглавными собственными значениями г, в, в < 0. Если А — индуцированный регулярный подграф из Г степени (I на ш вершинах, то

ги(к — сI) 5 <(1--^-- < г,

V — УО

причем одно из равенств достигается тогда и только тогда, когда каждая вершина из Г — Д смежна точно с т(к — (£)/(у — уо) вершинами из А.

Лемма 1.7. Пусть Г является сильно регулярным графом с собственными значениями к, 61,62 < 0, X, У — такие подмножества вершин из Г; что между X иУ нет ребер. Тогда выполняются следующие утверждения:

(1) \Х\ ■ |У| < (у - \Х\)(ь - - в2)У(2к -9,- 02)2;

(2) если \Х\ = \У\, то \Х\ < (у - \Х\)(в1 - в2)/{2к - в1 - в2).

Доказательство. Так как между X и У нет ребер, то по предложению 4.6.1 из [4] имеем \Х\ • \У\ < {у - - \У\){02 ~ 6'1)2/(2к ~02- 9{]2.

В случае \Х\ = |У| имеем \Х\ < (у - \Х\)(в2 - 00/(2к - 02 - 0{). Лемма доказана.

Изучение автоморфизмов дистанционно регулярных графов опирается на метод Хигмена приложения теории характеров конечных групп, представленный в третьей главе монографии Камерона [6]. При этом граф Г рассматривается как симметричная схема отношений (А', 71) с с1 классами, где X — множество вершин графа, Яо — отношение равенства на X и для 1>1 класс Щ состоит из пар (и, ш) таких, что с1(и, и>) = г. Для и 6 Г положим к$ = |Гг(-и)|,

V = |Г|. Классу Яг отвечает граф Г^ на множестве вершин X, в котором вершины гл, го смежны, если (и, т) £ Пусть А( — матрица смежности графа Г^ для г > 0 и А0 = I — единичная матрица. Тогда А^А^ = £ Р^А Для подходящих неотрицательных целых называемых числами пересечений графа Г.

Пусть Рг — матрица, в которой на месте Г) стоит Тогда собственные значения ^(О), ...,р\((1) матрицы Р\ являются собственными значениями графа Г кратностей т^ = Матрицы Р и (3, у которых на месте

(г,стоят стоят р^{г) и = /щ соответственно, называются пер-

вой и второй матрицей собственных значений схемы и связаны равенством

Р<2 = С}Р= \х\I.

Пусть и^ и Wj — левый и правый собственные векторы матрицы отвечающие собственному значению Р\(з) и имеющие первую координату 1. Тогда кратность т^ собственного значения р\(з) равна г»/гх?^). Фактически, г^-являются столбцами матрицы Р и т^и^ являются строками матрицы .

Подстановочное представление группы С = Аг^(Г) на вершинах графа Г обычным образом дает матричное представление ф группы С в С1/(п, С). Пространство О" является ортогональной прямой суммой собственных С-инвариантных подпространств И^о, •••, И^ матрицы смежности А = А\ графа Г. Для любого д Е С матрица ф(д) перестановочна с А, поэтому подпространство является ^((^-инвариантным. Пусть Хг — характер представления фцг1- Тогда для д Е С получим

а

Хг{д) = V'1 Е ¿=о

где — число точек х из X таких, что (х, х9) Е Щ. Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть

выражения для Хг(я) — число рациональное, то Хг(зО ~~ целое число.

Лемма 1.8 ([1, теорема 3.2]). Пусть Г — сильно регулярный граф с параметрами (и, /с, А, /л) и вторым собственным значением г. Если д — автоморфизм графа Г и Г2 = ¥\х(д), то |П| < у ■ тах{А,ц}/(к — г).

Глава 2. Расширения обобщенных четырехугольников

С<2(М)

Обобщенные четырехугольники имеют допустимые параметры

при £ Е {1,2,4,6,8,11,12,16}. Существование £) известно при £ £

{1,2,4,6,8,16}. При £ £ {11,12} неизвестно существование даже псевдогеометрических графов для С(3(4, ¿). При £ £ {1, 2,4,16} существуют единственные С<3(4,£) (для £ = 16 см. [30]).

В главе 2 доказано, что вполне регулярных локально С<3(4, 4)-графов нет (теорема 2.1) и получено описание вполне регулярных локально (7(5(4,6)-графов (теорема 2.2).

Подмножество Л обобщенного четырехугольника называется гиперовалом, если любая прямая пересекает Л по 0 или 2 точкам. То есть, гиперовал в СС^(з^) — это регулярный подграф без треугольников валентности £ + 1, имеющий четное число вершин. Известно (см. [7]), что /¿-подграфы в локально ¿)-графах являются гиперовалами. Для гиперовала А обобщенного четырехугольника прямую Ь назовем секущей, касательной и внешней прямой, если Ь П А содержит две, одну и ноль вершин соответственно; точку, смежную с ребром А, назовем реберной.

§ 2.1. Локально С(5(4,4)-графы

Основной результат параграфа

Теорема 2.1 [22]. Локально С(5(4,4)-граф не является вполне регулярным.

Пусть А — гиперовал из С(5(4, £) на ц вершинах. Положим X^ = Х;(Л), XI = Но лемме 1.2 имеем 10 < /л < 34. Если Ь — внешняя прямая для Л,

содержащая но точке из Х{, Х^,Х1, Хр,Хд, где i<j<l<p<q: то назовем Ь прямой типа (г, q). Если Ь — секущая прямая для Л, содержащая по точке из Х^, где г < j < то назовем Ь прямой типа (г, .7,1).

Лемма 2.1. Выполняются следующие утверждения:

(1) коэффициенты хг- удовлетворяют системе уравнений £¿=0 = 85 - ¡1 2гж2» = 15/х

£?=1 = 5//2/2 - 35///2.

(%) Если секущая Ь имеет тип (г, г), то i-\-j-\-r = p — А.

Доказательство. Первое утверждение следует из леммы 1.4.

Заметим, что Ь содержит две точки из А и каждая из этих точек смежна с 11 точками из А — Ь. Далее, каждая точка из А — Ь смежна с единственной точкой из Ь, поэтому (г — 2) + — 2) + (г — 2) = (д — 2) — 8. Лемма доказана.

Лемма 2.2. Выполняются следующие утверждения:

(1) если ц > 24, то Х0 является кокликой;

(2) если г Е ХГ, г = р — 24 и Ь — прямая, проходящая через г, то С [г] и либо

(г) Ь является секущей для А и содержит две точки из Хю, либо (гг) Ь — внешняя прямая для А, и если Ь пересекает то Ь содержит 3 точки из Х%.

Доказательство. Пусть р > 24. Если Хо содержит ребро, то на прямой, содержащей это ребро, имеются точки из Х^Д^Д; и I + у + I = р. Так как указанные точки лежат на внешней прямой, то каждое из чисел I не больше 8 и /г < 24. Итак, Х0 является кокликой. Утверждение (1) доказано.

Пусть г Е Хг, г = /1 — 24 и Ь — прямая, проходящая через г. Если Ь

является секущей для Л, то Ь — {г} содержит две точки из Х^, X) и по лемме 2.1 имеем г + 2 + г = // — 4. Отсюда г = 2 — 10. Если Ь — внешняя прямая для Ли Ь пересекает Х0, то Ь — (Хо и {г}) содержит 3 точки из XXj1 X/ и г + 2 + I = 24. Значит, 1 = 2=1 = 8-

Если у Е .Хо, £ — секущая, проходящая через г, то у смежна с единственной точкой прямой Ь. Так как указанная точка не попадает в Л и Хю, то

у е И-

Лемма 2.3. Выполняются следующие утверждения:

(1) если ¡1 = 32, то Хц содержит единственную вершину а, [а] = Х% и Г-(а1иА)= Х10;

(2) если /л = 30, то либо = 2, х§ = 5,ж8 = 30, жю = 18, либо — 0,^6 = 25,з:8 = 0,хю = 30 и Х§ является 5 х Ъ-решеткой.

Доказательство. Пусть ¡1 = 32. Тогда число секущих равно 80 и число внешних прямых равно 5. Далее, Х{ = 0 для г < 8. Отсюда Хо содержит единственную вершину а, по лемме 2.2 имеем [а] = Х% и Г — (а1 и Л) = Хю-Утверждение (1) доказано.

Пусть ¡1 = 30. Тогда число секущих равно 75 и число внешних прямых равно 10. каждая внешняя прямая имеет тип (6,6,6,6,6) или (0,6,8,8,8), а каждая секущая имеет тип (6,10,10) или (8,8,10), в частности, х2 = х^ = 0.

Так как вершина из Х% смежна с единственной вершиной из Хо и вершина из смежна с 15 вершинами из то = 15гео7 поэтому 16хо + Хе + х^ = 55 и 120х-0 + 6ж6 + Южю = 450. Отсюда 10ж0 + х6 = 25. Если х0 = 0, то хе = 25, х% = 0,жю = 30. В этом случае Х6 является 5 х 5-решеткой.

Если х0 = 1, то Жб = — 15,х10 = 24. В этом случае нет секущих типа (8,8,10), противоречие.

Если хо = 2, то х§ = b,xg = 30,= 18.

Ключевую роль в доказательстве теоремы 2.1 имеет следующий результат, полученный с помощью компьютерных вычислений.

Предложение 2.1. [23]. Пусть А является гиперовалом в С<5(4,4); ац — число вершин вне А, смеэюных точно с г вершинами из А. Тогда имеется 16 гиперовалов, попарно несопряженных относительно группы автоморфизмов С<5(4, 4) и выполняется одно из следующих утверждений:

(1) |Д| = 10 и х2 = 75;

(2) | Д | = 16, х0 = 3, х2 = 16, х4 = 48 и х8 = 2;

(3) |Д| = 18 и либо хо — 2,х2 ~ 15, х4 = 30, х6 = 20, либо х0 = 4, х2 = 9, х4 = 36, хо = 18;

(4) |Д| = 22 и либо хо — 2, х2 = 5, х4 = 20, Хб — 25, = 10, хю = 1, либо х2 = 15, хб = 45, жю = 3;

(5) |Д| = 24 и либо хо = 2,х2 = 4,х4 = 8,хс = 32, х8 = 11, Жю = 4, либо х0 = 6, х6 = 40, х8 = 15;

(6) |Д| = 26 и либо х0 = 2,х4 = 10, хв = 20, х8 = 20, хю = 7, либо х2 = 5, х6 = 40, Хю = 14;

(7) | Д | = 30 и либо х0 = 2, Хб = 5, х8 = 30, х10 = 18, либо х6 = 25, хю = 30;

(8) |Д| = 32, х0 = 1,х8 = 20, хю = 32;

(9) |Д| = 34 и х10 = 51.

До конца параграфа будем предполагать, что Г является связным вполне регулярным локально (2(^(4, 4)-графом с параметрами (г>, 85, 20, р).

Лемма 2.4. Диаметр Г не больше 3.

Доказательство. По лемме 1.2 имеем р(и,и>) > 10 для любых вершин и, ш б Г с (1(и, ш) = 2.

Пусть диаметр Г не меньше 4. Выберем геодезический 4-путь ишхуг в

Г. Тогда обобщенный четырехугольник [а;] содержит гиперовалы [и] П [х] и [х] П [г], между которыми нет ребер. Тогда /л(и, гс), (л(х, г) > 10 и [м] П [.т] содержится в Х0([а:]П[г]), противоречие с тем, что по предложению 2.1 имеем |Х0([а:] П < 6. Лемма доказана.

Лемма 2.5. Имеем ¡л е {16,34}, и диаметр Г равен 2 тогда и только тогда, когда ¡л = 34.

Доказательство. Так как к(к — А — 1) = к2[1, где к2 = 1^(^)1 для и £ Г, то ¡л делит 85 • 64. Отсюда /л = 10,16, 20, 32 или 34. По предложению случай /л = 20 невозможен, а в случаях /л = 10 и ¡л = 34 диаметр Г равен 2.

Если диаметр Г равен 2, то Г является сильно регулярным графом и (А — д)2 + 4(& — ¡л) = (20 — /¿)2 + 4(85 — ¡л) является квадратом натурального числа п. Отсюда /л = 10 или ¡л = 34.

В случае ¡л = 10 граф Г имеет параметры (630,85,20,10) и по [22] не существует. В случае ¡л = 32 граф Г имеет аффинные гиперовалы и по [18] не существует. Лемма доказана.

Завершим доказательство теоремы. Компьютерные вычисления показывают, что в С<5(4,4) для данного гииеровала А порядка 16 нет гиперовалов порядка 16, пересекающих А по 4 изолированным ребрам, противоречие с тем, что х8 = 2.

В случае гиперовала А порядка 34 имеем х10 = 51, противоречие с тем, что ввиду компьютерных вычислений найдется не более 17 гиперовалов порядка 34, пересекающих А по 5 изолированным ребрам.

§ 2.2. Вролне регулярные локально С(5(4,6)-графы

Точка х обобщенного четырехугольника называется регулярной,

если |({ж, 2/}^)^! = £ + 1 для любой точки у ф х1. Для регулярной точки х

обобщенного четырехугольника 5 = (Р, С) порядка (я, з) обобщенный четырехугольник Р(с>, х) порядка (5 — 1, 5 + 1) имеет множество точек Р' = Р — х1-и множество прямых состоящее из прямых £, не содержащих х, и гиперболических прямых ({ж, у}"1)-1, у £ хх.

Основной результат параграфа

Теорема 2.2 [27]. Пусть Г является связным вполне регулярным локально С(5(4, 6)-графом на V вершинах. Тогда V делится на 3 и выполняется одно из утверждений:

(1) диаметр Г равен 2, Г имеет параметры (726,125, 28, 20) и спектр 1251,15225, —7500;

(2) Г — дистанционно регулярный граф с массивом пересечений {125, 96,1; 1,48,125} на 378 вершинах и спектром 1251,1125, 542, -20168;

(3) Г - граф диаметра 3 с ¡1 е {20, 24, 25, 30, 32,40}.

Следствие 2.1. Пусть Г является дистанционно регулярным графом, в котором окрестность каждой вершины является обобщенным четырехугольником С(5(4,6). Тогда либо диаметр Г равен 2 и Г имеет параметры (726,125, 28, 20), либо Г - граф с массивом пересечений {125, 96,1; 1,48,125}.

Следствие 2.2. Пусть Г является связным вполне регулярным локально СС^(4,6)-графом, в котором окрестность некоторой вершины является известным обобщенным четырехугольником Р(\¥{Ь):х). Тогда Г — дистанционно регулярный граф с массивом пересечений {125, 96,1; 1,48,125}.

Начнем доказательство теоремы 2.2.

Лемма 2.6. Пусть обобщенный четырехугольник Р(Ж(5),х) порядка (4,6) содержит связный гиперовал А, Х{ = Х^А), Х{ = \Х{\. Тогда вы-

полняется одно из утверждений:

(1) |Д| = 20, х4 = 105;

(2) |Д| = 24, х0 = 2, х4 = 48, х6 = 48, х§ = 3 и Х0 является ребром;

(3) |Д| = 32, хо = 3,х4 = 9,х6 = 30, х8 = 30, жщ = 18,Х12 = 3 и Х0 является кокликой;

(4) |Д| = 36; х0 = 2,х2 = 4, х4 = 1,х6 = 10, х& = 30,х1О = 32,хх2 = 8, £14 = 2 и Хо является кокликой;

(5) |Д| = 40, хо = 5,х8 = 10, хю = 40,Х12 = 30 и Х0 является кокликой;

(6) |Д| = 44, х0 = 3,х§ = 1,хю = 18,Х12 = 45,Х14 = 14 и Х0 является кокликой;

(7) |Д| = 48 (две орбиты), х0 = 1,Х12 = 28,Х14 = 48.

Доказательство. Компьютерные вычисления.

Лемма 2.7. Пусть Г является связным вполне регулярным локально СС](4:6)-графом с параметрами (и, 125, 28, р). Тогда -и делится на 3 и выполняются следующие утверждения:

(1) р £ {20,24,25,30,32,40,48};

(2) если диаметр Г равен 2, то Г имеет параметры (726,125, 28, 20) и собственные значения 15 и —7 кратностей 225 и 500;

(3) диаметр Г не больше 3.

Доказательство. Имеем к — 125 и А = 28, поэтому V делится на 3, 20 < р < 50 и р делит 125 • 96. Отсюда р 6 {20,24,25,30,32,40,48,50}. Ввиду леммы 3 имеем .х0 < 25(125 — р)/{2Ъ + 7р).

Пусть диаметр Г равен 2. Тогда (А — /л)2 + 4{к — р) = п2, поэтому либо р = 20, п = 22, либо р = 40,п = 22, либо р = 50, п = 28. В первом случае Г имеет собственные значения 15 и —7. Во втором случае Г имеет собственные значения 5 и —17 с нецелыми кратностями. В третьем случае Г имеет

собственные значения 3 и —25 с нецелыми кратностями.

Допустим, что диаметр Г больше 3. Зафиксируем геодезический 4-путь и: ги, ж, у, г. Тогда [ж] П [г] С Х0([и] П [а;]). По лемме 1.2 имеем ¡л2 < (125 — /х)2/62, противоречие.

Лемма 2.8. Пусть Г — связный вполне регулярный локально 4,6)-граф с [л = 48. Тогда Г — дистанционно регулярный граф с массивом пересечений {125, 96,1; 1,48,125} на 378 вершинах и спектром 1251,1125, 542, -20168.

Доказательство. Если д = 48, то каждый /х-подграф является аффинным овоидом в 4,6) и ввиду теоремы из [18] заключение леммы выполняется. Лемма, а вместе с ней и теорема 2.2 доказаны.

Лемма 2.9. Пусть Г — дистанционно регулярный локально 4,6)-граф диаметра 3. Тогда /х = 48.

Доказательство. Пусть «¿(-а, из) = 2, Х0 = [ги] П П [ги]), ж0 = |Х0| и

= |Гг(и). Ввиду леммы 2 имеем ж0 < 25(125 — д)/(25 + 7/х).

В случае ¡л = 20 имеем А;2 = 125 • 96/20 = 600 и х0 < 15. Так как &1&2 делится на с2, то Ь2 Е {5,10,15}. В любом случае допустимых массивов пересечений нет.

В случае /л = 24 имеем /с2 = 125 -96/24 = 500 и жо < 13. Так как к2 сравнимо с 2 по модулю 3, то к3 сравнимо с 1 по модулю 3. В любом случае допустимых массивов пересечений нет.

В случае ¡л = 25 имеем к2 = 125 • 96/25 = 480 и ж0 < 12. Противоречие с тем, что Ь^ не делится на с2.

Список литературы диссертационного исследования кандидат наук Хамгокова, Мадина Мухадиновна, 2014 год

Литература

1. Behbahani М., Lam С. Strongly regular graphs with non-trivial automorphisms // Discrete Math. 2011, v. 311, N 2-3, 132-144.

2. Blokhuis A., Brouwer A.E. Locally 4-by-4 grid graphs //J. Graph Theory 1989, v. 13, 229-244.

3. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: Springer-Verlag - 1989.

4. Brouwer A.E., Haemers W.H. Spectra of graphs (course notes), http://www. win.tue.nl/ aeb/

5. Buekenhout F., Hubaut X. Locally polar spaces and related rank 3 groups // J. Algebra 1977, v. 45. 391-434.

6. Cameron P.J. Permutation Groups. London Math. Soc. Student Texts №45. Cambridge: Cambridge Univ. Press. 1999.

7. Cameron P., Hughes D. R., Pasini A. Extended generalized quadrangles // Geom. Dedic. 1990, v. 35. 193-228.

8. Jurisic A., Koolcn J. Classification of the family AT4(gs,g, q) of antipodal tight graphs // J. Comb. Theory 2011, v. 118, N 3, 842-852.

9. Prager C.E., Soicher L.H. Low rank representations and graphs for sporadic groups. Lecture series 8. Cambridge, University press, 1997.

10. Seidel J.J. Strongly regular graphs with (—1,1,0) adjacency matrix having eigenvalue 3 // Lin. Alg. Appl. 1968, v. 1, 281-298.

11. Tits J. Buildings of Spherical Type and finite BN-pairs, Springer Lecture Notes in Mathematics, v. 386, 1974.

12. Гаврилюк A.JI., Махнев А.А. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {56, 45,1; 1, 9, 56} // Доклады академии наук 2010, т. 432, N 5, 512-515.

13. Кагазежева А.М. О локально GQ(4,ll)-rpa4)ax // Математический форум (Итоги науки. Юг России), т. 6. Группы и графы, Владикавказ 2012, 28-39.

14. Кондратьев A.C. Граф Грюнберга-Кегеля конечной группы и его приложения // Алгебра и линейная оптимизация. Труды межд. семинара. Екатеринбург 2002, 141-158.

15. Махнев A.A. Конечные локально СС^(3,3)-графы // Сиб. матем. ж. 1994, т. 35, N 6, 1314-1324

16. Махнев A.A. Локально СС^)(3,5)-графы и геометрии с короткими прямыми // Дискр. матем. 1998, т. 10, N 2, 72-86.

17. Махиев A.A., Падучих Д.В. О структуре связных локально GQ(3,9)-графов // Дискр. анализ и иссл. опер., сер. 1 1998, т.5, N 2, 61-77.

18. Махнев A.A. Аффинные овоиды и расширения обобщенных четырехугольников // Матем. заметки 2000, т. 68, N 2, 266-271.

19. Махнев А. А., Падучих Д.В. Расширения GQ(4,2), вполне регулярный случай // Дискретная математика 2001, т. 13, N 3, 91-109.

20. Махнев A.A. Псевдодвойственные решетки и расширения обобщенных четырехугольников // Сиб. матем. журнал 2001, 42, N 5, 1117-1124.

21. Махнев A.A. Протопопова В.Е. О вполне регулярных локально GQ(s, ¿)-графах c/¿ = 2í + 6 // Известия Гомельского госун-та 2003, т. 4, 68-81.

22. Махнев A.A. О сильно регулярных локально GQ(4,t) графах // Сибирский матем. журнал 2008, 49, N 1, 161-182.

23. Махнев A.A., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально С(^(4,4)-графах // Доклады академии наук 2010, т. 434, N 5, 583586.

24. Махнев A.A., Падучих Д.В., Хамгокова М.М. О вполне регулярных

локально GQ(4,6)-rpac[)ax // Современные проблемы математики. Тез. докл. 43 Международной молод, конф. Екатеринбург 2012, 66-68.

25. Махнев A.A., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально С(^)(5,3)-графах // Теория групп и ее приложения. Труды восьмой Международной школы-конференции по теории групп. Нальчик 2010, 173179.

26. Махнев A.A., Падучих Д.В. О вполне регулярных локально GQ(5,5)-графах // Доклады академии наук 2010, т. 435, N 1, 18-21.

27. Махнев A.A., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально GQ(5,3)-графах // Доклады академии наук 2010, т. 435, N 6, 744747.

28. Махнев A.A., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально С(^(4,6)-графах // Доклады академии наук 2012, т. 444, N 2, 146149.

29. Махнев A.A., Падучих Д.В. О вполне регулярных локально GQ(4,8)-графах // Доклады академии наук 2012, т. 446, N 2, 127-130.

30. Махнев A.A., Падучих Д.В., Хамгокова М.М. О локально GQ(5,3)-графах // Алгебра и комбинаторика. Тез. докл. Международной конф., посвященной 60-летию A.A. Махнева, Екатеринбург 2013, 53-55.

31. Махнев A.A., Падучих Д.В. Обобщенный четырехугольник GQ(4,16) и его расширения // Доклады академии наук 2013, т. 451, N 4, 378-380.

32. Махнев A.A., Падучих Д.В., Хамгокова М.М. Дистанционно регулярные локально псевдо GQ(5, 3)-графы // Доклады академии наук 2014, т. 458, N 5.

33. Махнев A.A., Падучих Д.В., Хамгокова М.М. Дистанционно регулярные локально псевдо GQ(5, 3)-графы // Тез. докл. X Международной школы-

конференции по теории групп, посвященной 70-летию В.В. Кабанова, Нальчик 2014, 43-45.

34. Нирова М.С. Дистанционно регулярные локально СС^(4,12)-графы // Сибирские электрон, матем. известия 2013, т. 10, 144-150.

35. Хамгокова М.М. Локально ^(^(4,4)-графы: описание гиперовалов // Перспектива 2009. Материалы межд. конф. студентов, аспирантов и молодых ученых, т. 8, КБГУ, Нальчик, 124-128.

36. Хамгокова М.М. Об автоморфизмах сильно регулярного графа с параметрами (322,96,20,32) Математический форум (Итоги науки. Юг России), т. 6. Группы и графы, Владикавказ 2012, 162-170.