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

• Кагазежева, Алена Мухамедовна
• кандидат наук
• 2015

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

ОГЛАВЛЕНИЕ

Введение

Глава 1. Локально 4,11)-графы § 1.1. Вспомогательные результаты § 1.2. Большие гиперовалы в 11)

§ 1.3. Локально (Д)(4,11)-графы

Глава 2. Автоморфизмы сильно регулярных графов с параметрами (96,45, 24,18) и (320,99,18,36)

§ 2.1. Сильно регулярный граф с параметрами (96,45,24,18) § 2.2. Графы с параметрами (96,45,24,18) и (96,50,22,30) не являются ре-берно симметричными

§ 2.3. Сильно регулярный граф с параметрами (320,99,18,36) Глава 3. Дистанционно регулярные графы, в которых окрестности вершин сильно регулярны со вторым собственным значением

§ 3.1. Графы, в которых окрестности вершин сильно регулярны с параметрами (111,30,5,9)

§ 3.2. Графы, в которых окрестности вершин сильно регулярны с параметрами (169,42,5,12)

Глава 4. Автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1,42,169}

§ 4.1. Автоморфизмы графа с параметрами (169,42, 5,12) § 4.2. Автоморфизмы дистанционно регулярнго графа с массивом пересечений

§ 4.3. Дистанционно регулярный граф с массивом пересечений {169,126,1; 1,42,169}, вершинно симметричный случай Литература

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

Введение

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

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

Дж. Кулен предложил задачу изучения дистанционно регулярных графов, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением, не большим t для данного натурального числа t. Заметим, что сильно регулярный граф с нецелым собственным значением является графом в половинном случае, а вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы с к = 2либо имеет диаметр 2, либо являеься графом Тэйлора. Таким образом, задача Кулена может быть решена пошагово для £=1,2,....

Задача Кулена решена для t = 1 (окрестности вершин — графы, дополнительные кзейделевым) Кардановои M.J1. и Махневым A.A. в [4] и независимо Куленом. Случай t — 2 изучался более 10 лет и завершен в статье И.Н. Бело-

усова, A.A. Махнева и М.С. Нировой [5]. Рассмотрение случая t = 3 начато в статье A.A. Махнева [6] (теорема редукции) и A.A. Махнева и Д.В. Падучих [7] (список параметров исключительных графов).

Диссертация вносит существенный вклад в решение задачи Кулена для t = 3. Ее цель — изучить локально GQ{4,11)-графы, найти автоморфизмы сильно регулярных графов с параметрами (96,45,24,18) и (320,99,18,36), перечислить массивы пересечений дистанционно регулярных графов, в которых окрестности вершин сильно регулярные графы со вторым собственным значением 3 и параметрами (г/, к', 5, //) и найти автоморфизмы возникших графов.

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

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

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

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

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

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

Число вершин в [а] П [Ь] обозначим через А(а,&), если d(a,b) = 1, а соответствующий подграф назовем Л -подграфом.

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

Если вершины u,w находятся на расстоянии г в Г, то через Ьг(и,и;) (через Ci(u.w)) обозначим число вершин в пересечении ri+i(w) (rz_i(n)) с Г(w). Заметим, что в реберно регулярном графе число bi(u,w) не зависит от выбора смежных вершин и, w и равно Ь\ — к — А — 1.

Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {&о, Ь\,..., öd-i; ci,..., q}, если значения bi(u, w) и q(w, w) не зависят от выбора вершин w, w на расстоянии г в Г для любого г = 0,d.

Система инцидентности, состоящая из точек и прямых, называется а-частичной геометрией порядка (s,£), если каждая прямая содержит ровно s + 1 точку, каждая точка лежит ровно на ¿ + 1 прямой (прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется ровно а прямых, проходящих через а и пересекающих L (обозначение pGa(s: t)). Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на общей прямой (коллинеарны). Легко понять, что точечный граф частичной геометрии pGa(s,t) сильно регулярен с параметрами: v = (s-bl)(l + .si/o:), к — s(i + l), Л = (s — 1) + (ог —

¡л — а(1 + 1). Сильно регулярный граф с такими параметрами для некоторых натуральных чисел а, в, I называется псевдогеометрическим графом для

рСЦМ)-

Для подграфа А графа Г через Х{(А) обозначим множество всех вершин из Г — А, смежных точно с г вершинами из А, и положим хг-(А) = |^(Д)|.

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

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

Через К7Пи...!ТПп обозначим полный п-дольный граф, с долями порядков т1, .■■■)тп1г. Если гп\ = ... = тпп = гп, то соответствующий граф обозначается через Кпх?п (и является локально К(п-])хт-графом)• Граф называет-

ся т-лапой. Графом Тэйлора называется дистанционно регулярный граф с массивом пересечений {А;, д, 1; 1, к].

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

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

Задача описания локально ¿)-графов (графов, в которых окрестно-

сти вершин являются точечными графами для ¿)) является классиче-

ской и решена для я < 3 (см. [8-12]).

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

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

- доказано что сильно регулярный граф с параметрами (96,45,24,18) не является реберно симметричным,

- найдены автоморфизмы сильно регулярного графа с параметрами (320,99, 18,36),

- найдены массивы пересечений дистанционно регулярных графов, в которых окрестности вершин сильно регулярные графы со вторым собственным значением 3 и параметрами (г/, А/, 5, //),

- найдены автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1,42,169}.

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

Основные результаты работы докладывались на алгебраическом семинаре отдела алгебры и топологии ИММ УрО РАН, а также были представлены на следующих конференциях: Теория групп и ее приложения, IX Международная школа-конференция по теории групп, Владикавказ 2012 г., Международная конференция по теории групп, посвященная 70-летию В.Д. Мазурова, Новосибирск 2013 г., Международная школ а-конференция "Группы и графы, алгоритмы и автоматы" , посвященная 80-летию В.А. Белопогова и 70-летию

В.А. Баранского, Екатеринбург 2015 г.

По теме диссертации имеется 8 публикаций [13-20] (четыре статьи опубликованы в журналах из списка ВАК). Из пяти статей две написаны без соавторов, одна - тремя авторами (Кагазежева A.M., Журтов А.Х., Махнев A.A.), две в соавторстве с Махневым A.A. В работе трех авторов Журтов А.Х. и Махнев A.A. уточнили доказательство, предложенное Кагазежевой A.M. В работах двух авторов Махневу A.A. принадлежат только постановки задач и рассуждения, связанные с применением модулярных представлений.

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

В главе 1 приведены вспомогательные результаты и доказано несуществование дистанционно регулярных локально GQ(4,11)-графов. В главе 2 найдены автоморфизмы сильно регулярных графов с параметрами (96,45,24,18) и (320,99,18,36). В главе 3 - найдены массивы пересечений дистанционно регулярных графов, в которых окрестности вершин сильно регулярные графы со вторым собственным значением 3 и параметрами (v',k', 5,//). В главе 4 найдены автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1,42,169}.

Обобщенные четырехугольники GQ(4,t) имеют допустимые параметры при t Е {1,2.4,6,8,11,12,16}. Существование GQ(4,t) известно при t £ {1,2,4,6,8,16}. При t е {11,12} неизвестно существование даже псевдогеометрических графов для GQ(4, t). Имеется сле/1ующее предположение

Гипотеза. Если GQ(s,t) существуют, то число s + i четно.

В случае GQ(3, t) единственное допустимое четное значение t равно 6. Однако GQ(3,6) (и даже псевдогеометрический граф для GQ(3, 6)) не суще-

ствует [21]. Таким образом, 4,11) — наименьший обобщенный четырехугольник, который может стать контрпримером к этой гипотезе.

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

Теорема 1 [13]. Пусть Г является связным вполне регулярным локально (7(2(4,11)-графом с параметрами (у, к, Л, /.¿). Тогда диаметр Г равен 3 и ¡1 Е {48,50, 60, 66, 72}, причем в случае ц = 72 для любой вершины и подграф Гз(м) является кокликой, содержащей не более 20 вершин.

Ключевую роль в доказательстве теоремы 1 имеет следующий результат.

Предложение 1 [13]. Пусть А является гиперовалом в С(3(4,11) на ¡1 вершинах, X^ — множество вершин вне А, смежных точно с % вершинами из А, Х{ = |Хг|. Тогда выполняются следующие утверждения:

(1) если > 66, то .Хо является кокликой;

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

(г) Ь является секущей для Л и содержит две точки из Х24, либо (И) Ь — внешняя прямая для А, и если Ь пересекает то Ь содер-эюигп 3 точки из Х<х1-

Следствие 1. Локально СС^)(4:, 11 )-граф не является дистанционно регулярным.

В главе 2 изучены автоморфизмы сильно регулярных графов с параметрами (96,45,24,18) и (320,99,18,36) (имеющих второе собственное значение 3).

Бехбахани и Лам [23] нашли параметры неизвестных сильно регулярных графов с числом вершин, не большим 100.

Предложение 2. Пусть Г — неизвестный сильно регулярный граф с числом вершин, не большим 100, имеющий неединичный автоморфизм, и £ = Аи1(Г). Тогда выполняется одно из следующих утверждений:

(1) Г имеет параметры (85,30,11,10) и -к(С) = {2,3, 5,17};

(2) Г имеет параметры (85,54,33,36) и {3,5,17} С тг(С) С {2,3,5,17};

(3) Г имеет параметры (88,27, 6,9) и {2,3,11} С 7г(С) С {2,3,5,11};

(4) Г имеет параметры (88,60,41,40) и -к{О) = {2,3,5,11};

(5) Г имеет параметры (96,45,24.18) и 7г((2) = {2,3,5};

(6) Г имеет параметры (96,50,22,30) и 7г(С) = {2,3,5};

(7) Г имеет параметры (96,60,38,36) и 7г((7) = {2,3,5};

(8) Г имеет параметры (99, 42,21,15) и {2,3, 7,11} С тг(С) С {2, 3,5, 7,11};

(9) Г имеет параметры (99, 56,28,36) и {2,3, 7,11} С тг(£) С {2, 3, 5, 7,11};

(10) Г имеет параметры (100,33,8,12) и 7г(6?) = {2,3,5,11};

(11) Г имеет параметры (100, 66,44,42) и 7г(<3) = {2, 3, 5,11}.

А. А. Махнев и М.С. Нирова предложили программу изучения реберно симметричных графов с параметрами из заключения предложения 2. Следующий результат является вкладом в эту программу

Теорема 2 [14]. Пусть Г — сильно регулярный граф с параметрами (96,45,24,18), д — элемент простого порядка р из АиЬ(Г) и А = Г1х(д). Тогда выполняется одно из следующих утверждений:

(1) А — пустой граф, либо р = 3 и а\(д) 6 {0,36,72}, либо р = 2 и а1{д)£{0,24,48,72,

96};

(2) Д является (3-кликой, либо

(г) р = 2, (3 четно, 4 < Р < 16 и 3(3 + а>\(д) делится на 24, либо (И) р = 5, (3 = 1 и а\{д) = 45 мл« Р = 6 г/ на Г — Д имеем восемь-надцатъ кликовых (д)-орбит, или (3 = 11 и на Т — Д имеем тринадцать кликовых и четыре пятиугольных (д) -орбит, или (3 = 16 и на Г — А имеем по восемь кликовых и пятиугольных (д)-орбит;

(3) Д является 7-кокликой, р = 3 и либо 7 = 3, а\(д) £ {27,63}, либо 7 = 6, а1(д) е {18,54,90};

(4) р~3, либо |Д| £ {6,9,12} и 3| Д| -\-а\(д) делится на 36, либо |Д| = 24 и аг(д) = 72;

(5) р = 2, либо 4 < |Д[ < 40 и 3|Д| + а\(д) делится на 24, либо |Д| = 48, любая вершина из А смежна с вершиной из Г — Д и а\(д) = 48.

Следствие 2. Сильно регулярные графы с параметрами (96,45, 24,18) и (96, 50,22, 30) не являются реберно симметричными.

Несуществование псевдогеометрического графа для р(?2(5,32) доказано в [24]. Псевдогеометрический граф для 5,32) имеет сильно регулярные подграфы — окрестность вершины (псевдогеометрический граф для 8))

и вторую окрестность вершины (граф с параметрами (320,99,18,36)). В следующей теореме найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (320,99,18,36). Этот результат завершает описание автоморфизмов локальных подграфов в изорегулярном графе 1го{3) (псевдогеометрическом графе для £>Сз(6, 80)), см. [25-27].

Теорема 3 [15]. Пусть Г является сильно регулярным графом с пара-

метрами (320, 99,18, 36), С = Аи^С), д — элемент простого порядка р из С, П = ¥ж(д). Тогда 7г(<3) С {2,3,5,7,11} и выполняется одно из следующих утверждений:

(1) П — пустой граф, р = 5 и а\(д) Е {0,120} или р = 2 и а\(д) е {0,48,96,144,192,240,

288};

(2) О является одновершинным графом, р — 11 и сч\(д) = 66;

(3) О является т-кокликой, р = 3, т = 3/. + 2, 3 < I < 14 и а\(д) — 9т —6 делится на 72;

(4) П — объединение I изолированных ребер, 2<1<29р = 2и ац(д) - Ы делится на 48;

(5) р = 11 и либо

(г) |0| = 67 и оц{д) = 33, либо

(И) = 78 и а>1 (д) = 66, либо

(иг) =89 и ац(д) = 99;

(6) р — 7 и либо

(г) П = Х3х4 и ац(д) е {84, 252}, либо

(и) |0| = 7в + 5, 2 < й < 10, а\(д) = 21г и б — г + 3 делится на 8, либо

(Иг) |П| = 96 и ах(д) = 0;

(7) р = 5 и либо

(г) |П| = 90, а\(д) = 90, на Г —О, имеются 36 пятиугольных (д)-орбит и 10 кокликовых;

(И) |0| = 85, а\(д) = 15, наГ — О, имеются 6 пятиугольных (д)-орбит и 41 кокликовая;

(иг) |П| = 80, а\(д) Е {0,120}, на Г — П имеются 48 пятиугольных (д)-орбит или 48 кокликовых;

(iv) |ii| = 5s, 3 < s < 15, ai(g) = 120r + 15s, r e {-2, -1, 0,1,2};

(8) p = 3, I ¡571 = 3i + 2, П не содержит вершин степени |f)| — 2 и либо (г) О. является объединением двух изолированных вершин и К^;з-под-

графа, щ{д) делится на 72, либо

(и) \й\ — 80 или |0| = 140 и o>i(g) = 0, либо

(Ш) |fi| = 3i + 2, 3 < t < 25, a^g) = 72s + 9t + 54 и s e {-3, -2,4};

(9) p = 2 и либо

(г) il — куб и a\{g)/2A — нечетное натуральное число, либо

(и) щ(д) = 0, |0| = 16s, s G {1, 2,..., 9}, либо

(ш) суЛ(д) ± О, \П\ = 2t, 5 < t < 70 и аг(д) = 48г + 6t.

В [7] найдены параметры исключительных сильно регулярных графов с неглавным собственным значением 3. Отсюда следует

Предложение 3. Пусть Г - исключительный сильно регулярный граф с неглавным собственным значением 3. Если Л = 5, то Г имеет параметры (21,10,5,4), (111,30,5,9) или (169,42,5,12).

В третьей главе диссертации изучены вполне регулярные графы, в которых окрестности вершин сильно регулярны с параметрами (111,30,5,9) или (169,42, 5,12). Существование графов с параметрами (111, 30, 5, 9) и (169, 42, 5,12) неизвестно.

Теорема 4 [16]. Пусть Г — вполне регулярным граф, в котором окрестности вершин — сильно регулярные графы с параметрами (111,30,5,9), и — вершина графа Г и ki — |Гг(и)|. Тогда (¿(Г) = 3, ка четно и выполняется одно из утверждений:

(1) ц = 30, 2 < к3 < 18;

(2) ¡1 = 40, 2 < < 8 и Гз является объединением изолированных вершин

и ребер.

Теорема 5 [16]. Пусть Г — вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы с параметрами (169,42, 5,12), и — вершина графа Г и /сг- = |ГДи)|. Тогда с£(Г) = 3 и выполняется одно из утверждений:

(1) /7, = 39, А:3 четно, 2 < к3 < 20;

(1) р = 42, к% нечетно, 3 < < 15;

(3) р = 63, кз четно, 2 < к^ < 12 и Г3 является объединением изолированных вершин и ребер.

Следствие 3. Пусть Г дистанционно регулярный граф, в котором окрестности вершин — сильно регулярные графы с собственным значением 3 и параметрами (г/, к', 5, //). Тогда окрестности вершин либо изоморфны треугольному графу Т(7) и Г — половинный граф 7-куба, либо сильно регулярны с параметрами (169,42,5,12) и Г имеет массив пересечений {169,126,1; 1,42,169}.

В главе 4 изучаются автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1, 42,169}.

Теорема 6 [17]. Пуст,ь Г — дистанционно регулярный граф, имеющий массив пересечений {169,126.1; 1,42,169}, С? = Аи1;(Г), д — элемент из простого порядка р и О. = ¥1х(д) содержит по в вершин в I антиподальных классах. Тогда 7г((?) с {2,3,5,7,11,13,17, 19} и выполняется одно из следующих утверждений:

(1) П — пустой граф и либо

(г) р = 17, а\(д) = 16 • 17, а2(д) = 24 • 17, либо

(и) р = 5, а\(д) = 5(26га + 8) и о;2(д) = 5(128 — 26т), либо

(т) р = 2, а3{д) = 41, аг{д) = 170+26т+12/ и а2(д) = 510-26т-16/;

(2) р = 19, либо П — дистанционно регулярный граф с массивом пересечений {17,12,1;

1,4,17}, либо £ = 37;

(3) р = 13, либо О — антиподальный класс, либо О — дистанционно регулярный граф с массивом пересечений {13,9,1; 1, 3,13}, либо £ = 27,40;

(4) р — 11 и О, — дистанционно регулярный граф с массивом пересечений {37, 27,1; 1,9,

37};

(5) р = 7 и £ = 2,9,16,23,30,37;

(6) р = 5, либо П — дистанционно регулярный граф с массивом, пересечений {9, 6,1; 1, 2,

9}, либо г = 15,20,25,30,35,40;

(7) р = 3, либо в = 4 и £ = 2,5,8, ...,41, либо й = 1, П является Ь-кликой и г = 2,5,8,11,14;

(8) р — 2,1 четно и либо $ = 4, I < 42, ушбо я = 2 и £ < 86.

Теорема 7. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {169,126,1; 1,42,169}, в котором окрестности вершин сильно регулярны с параметрами (169,42,5,12), = Аи1;(Г), д — элемент из (7 простого порядка р > 2 и П = ¥Ъс(д) — непустой граф, содерэюащий по б вершин в £ ангпиподальных классах. Тогда тг(С) С {2,3,5, 7,13,17} и выполняется одно из следующих утверждений:

(1) некоторая (д)-орбита на Г — П содержит геодезический 2-путь, либо р = 7 и £ = 2, либо р = 5 и Г2 — дистанционно регулярный граф с массивом, пересечений {9,6,1; 1, 2,9};

(2) некоторая {д)-орбита на Г — О, является кликой, р = 3 и либо в = 4,

£ = 2, 5 и П является объединением четырех изолированных 1-клик, либо

5 = 1 и О является 2-кликой;

(3) каждая (д)-орбита паТ — О, является кокликой и либо р — 13, П — антиподальный класс, либо р = 5 и I — 40, либо р = 3, в = 4 и t = 14.

Следствие 4. Пусть Г — дистанционно регулярный граф с массивом пересечений {169,126,1; 1,42,169}, в котором окрестности вершин сильно регулярны с параметрами (169,42,5,12). Если С = Ли^Г) неразрешимая группа, действующая транзитивно на множестве вершин графа Г, то Б — б'(С) является элементарной абелевой 2-группой, факторгруппа

6 = С/б1 изоморфна 5^4(4), для вершины а £ Г имеем Са = 26 : [7,^ х А5), содержит нормальную в С подгруппу К порядка 4, регулярную на каждом антиподальном классе, ^ : = 2 для антиподального класса Р, 5/К является неприводимым Р23р^(4)-модулем порядка 28, 216 или 232 и СМ/) = К для элемент,а / порядка 17 из С.

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

«3(4,11)

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

Метод Г. Хигмена [27]. Граф Г рассматривается как симметричная схема отношений (Х,71) с дь классами, где X —- множество вершин графа, И® — отношение равенства на X и для г > 1 класс состоит из пар (и, ио) таких, что в,(и,1п) = г. Для и Е Г положим к( = |Гг(к)|, V = |Г|. Классу Я{ отвечает граф Гг на множестве вершин X, в котором вершины и:и; смежны, если (■и,и;) Е .Яг. Пусть А{ — матрица смежности графа Г^ для г > 0 и Ао = I — единичная матрица. Тогда А{А^ — для подходящих неотрицательных

целых р' -, называемых числами пересечений графа Г.

Пусть Р{ — матрица, в которой на месте /) стоит р\у Тогда собственные значения £>1(0),...,рх(с?) матрицы Р\ являются собственными значениями графа Г кратностей то = Матрицы Р и (5, у которых на месте

(1,3) стоят стоят р^ъ) и qj(i) ~ т^р^э)/к{ соответственно, называются первой и второй матрицей собственных значений схемы и связаны равенством

Р(2 = <2Р = \х\1.

Пусть и^ и и>2 — левый и правый собственные векторы матрицы Р\1 отвечающие собственному значению р\(з) и имеющие первую координату 1. Тогда кратность т^ собственного значения р\{з) равна ш^) ((•, •) — скалярное

произведение в евклидовом пространстве С^+1). Фактически, иявляются столбцами матрицы Р и тявляются строками матрицы С}.

Подстановочное представление группы (7 = Аи^Г) на вершинах графа Г обычным образом дает матричное представление ф группы (7 в СЬ(п, С). Пространство С" является ортогональной прямой суммой собственных 6г-

инвариантных подпространств ..., матрицы смежности А ~ А\ графа Г. Для любого д Е (7 матрица ф(д) перестановочна с А, поэтому подпространство \¥{ является ^(С)-инвариантным. Пусть \г ~ характер представления . Тогда для д Е (7 получим

(1

Хг{д) = £ Яа<хз{9),

з=о

где а^{д) — число точек х из X таких, что (1(х, х9) = у. Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть выражения для Хг{9) ~ число рациональное, то Хг(<?) — целое число.

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

Лемма 1.1. Пусть Г — локально С(^(8^)-граф. Тогда максимальные клики из Г состоят из в + 2 точек (такие клики мы будем называть блоками), каждая точка лежит в (£ + 1)(з£ -I- 1) блоках, любые две смежные тючки леоюат в £ +1 общих блоках, любые два блока пересекаются не более чем по двум точкам.

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

Лемма 1.2. Пусть А — гиперовал в обобщенном четырехугольнике СС^^^), ¡1 = |А|. Тогда у четно, и выполняются следующие утверждения:

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

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

(3) ухо <{и- у){у - х0)(г + 5)7(25(£ + 1) + г + 2 - й)2.

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

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

Так как между Л и Хо нет ребер, то по предложению 4.6.1 из [29] имеем ух0 <(у-у)(у- хо)(Ог - 02)7(2А; - вг - 62)\ где в2 = + 1), в1 = з - 1 -неглавные собственные значения графа Г. Поэтому ухо < (у — у) (у — жо)(£ +

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

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

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

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

-к(1 + 1)(к-1) = к(г + 1){к-г)

(к + г1){г-1) Я~ (к + г1){г-1)

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

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

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

Лемма 1.4. Пусть Г - сильно регулярный граф, имеющий параметры (■V, к, А, у), А - индуцированный подграф с N вершинами, М ребрами и степенями вершин ¿1,..., Тогда =у-И, гх1 = кИ - 2М, Е£2 (')*,■ = ХМ + у({») — М) — Е Й)■

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

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

(1) /2 делит Ьф{+ъ 1 и а2(а2 — а^ + 62с3 — к;

(2) с2 делит Ъ¿(а^ + а*+1 — а\) и с1+г(а1 + а¿+1 - сц);

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

Доказательство. Утверждения (1-2) следуют из леммы 4.1.7 [2] (например, утверждение (1) следует из целочисленности ^¿"-ъ 7+1 и Рж)-Утверждение (3) следует из теоремы 4.4.4 [2].

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

гп(к — д)

з<с1----- < г,

V — и)

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

Лемма 1.7. Пусть Г является сильно регулярным графом с собственными згшчениями к,0\,62 < 0, X, У — такие подмножества вершин из Г, что между X и У нет ребер. Тогда выполняются следующие утверждения: (1) \Х\ ■ \У\ <(у- \Х\){у - |У|)(0! - 02)7(2 к -вг- в2)2;

(2) если \Х\ = |У|, то \Х\ < (v - |X|)(<9i - в2)/(2к - в1 - в2).

Доказательство. Так как между X и У нет ребер, то по предложению

4.6.1 из [29] имеем \Х\ ■ |У| < {v - \X\)(v - |У|)(02 - вг)2/(2к - в2 - в{)2. В случае \Х\ = |У| имеем \Х\ < (v - |Х|)(02 - 0г)/(2к - в2 - в{). Лемма

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

§ 1.2. Большие гиперовалы в С(5(4,11)

В этом параграфе предполагается, что Г является точечным графом обобщенного четырехугольника 4,11), А — гиперовал из Г на р вершинах.

Положим Х{ — Хг(Л), Х{ — \Хг\. По лемме 1.2 имеем 45 < р, < 90. Если Ь — внешняя прямая для Л, содержащая по точке из Хг. Х3. X/, Хр: ХС}1 где г < 2 < I < р < д, то назовем Ь прямой типа (г,^', 1,р, q). Если Ь — секущая прямая для Л, содержащая по точке из Х^Х^^Х^ где г < э < I, то назовем Ь прямой типа /).

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

(1) коэффициенты Х{ удовлетворяют системе уравнений

(2) Если секущая L имеет тип (i,j,r), то г + j + г = р — 18.

Доказательство. Первое утверждение следует из леммы 1.4. Заметим, что L содержит две точки из Л и каждая из этих точек смежна с 11 точками из Л — L. Далее, каждая точка из Л — L смежна с единственной

Список литературы диссертационного исследования кандидат наук Кагазежева, Алена Мухамедовна, 2015 год

Литература

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

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

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

4. Карданова M.JI., Махнев А.А. О графах, в которых окрестности вершин являются графами, дополнительными к графу Зейделя // Доклады академии наук 2010. Т. 434, N 4. С. 447-449.

5. Белоусов И.Н., Махнев А.А., Нирова М.С. Дистанционно регулярные графы, в которых окрестности вершин сильно регулярны с собственным значением 2 // Доклады академии наук 2012. Т. 447, N 5. С. 475-478.

6. Махнев А.А. О сильно регулярных графах с собственным значением 3 и их расширениях // Доклады академии наук 2013. Т. 451, N 5. С. 475-478.

7. Махнев А.А., Падучих Д.В. Исключительные сильно регулярные графы с собственным значением 3 // Труды Института математики и механики 2013. Т. 19, N 4. С. 167-174.

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

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

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

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

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

13. Кагазежева A.M. О локально С(^(4,11)-графах // Математический форум (Итоги науки. Юг России), т. 6. Группы и графы, Владикавказ 2012, 28-39.

14. Журтов А.Х., Кагазежева A.M., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (96,45,24,18) // Доклады академии наук 2012, т. 446, № 1, 10-14.

15. Кагазежева A.M., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (320,99,18,36) // Владикавказский математический журнал 2013, т. 15, n 2, 61-71.

16. Кагазежева A.M., Махнев А.А. О графах, в которых окрестности вершин сильно регулярны с параметрами (111,30,5,9) или (169,42,5,12) // Доклады академии паук 2014, т. 456, № 2, 135-139.

17. Кагазежева A.M. Автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1,42,169} // Сибир. электрон, матем. известия 2015, т. 12, 318-327.

18. Журтов А.Х., Кагазежева A.M., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (96,45,24,18) // Теория групп и ее приложения. Тез.докл. Межд. школы-конф. Владикавказ 2012, 58-59.

19. Kagazezheva A.M., Makhnev А.А. On graphs whose vertex neighborhoods are strongly regular with parameters (111,30,5,9) or (169,42,5,12) // The International Conference on Group Theory in Honor of the 70th Birthday of Professor Victor D. Mazurov. Abstracts, Novosibirsk 2013, 81.

20. Kagazezheva A.M. Automorphisms of graph with intersection array {169, 126,1; 1,42,169} // "Groups and Graphs, Algorithms and Automata". Abstracts,

Ekaterinburg 2015, 43.

21. Махнев А.А. О псевдогеометрических графах некоторых частичных геометрий // Вопросы алгебры, Гомель: Изд-во Гомельского ун-та, 1997, т.11, 60-67.

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

23. Behbahani M., Lam C. Strongly regular graphs with non-trivial automorphisms // Discrete Math. 2011, v. 311, N 2-3, 132-144.

24. Махнев А.А. О несуществовании сильно регулярных графов с параметрами (486,165,

36,66), Украинский матем. журнал 2002, т. 54, N 7, 941-949.

25. Махнев А.А., Нирова М.С. Об автоморфизмах сильно регулярного графа с параметрами (640,243,66,108) // Доклады академии наук 2011, т. 440, N 6, 743-746.

26. Исакова М.М., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (396,135,30,54) // Труды Института математики и механики 2010, т. 16, N 3, 96-104.

27. Махнев А.А., Токбаева А.А. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) // Труды Института математики и механики 2010, т. 16, N 3, 185-194.

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

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

30. Махнев А.А. О сильно регулярных локально GQ(4, ¿)-графах // Сибирский матем. журнал 2008, т. 49, N 1, 1811-1826.

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

32. Махнев A.A., Нирова М.С. О небольших симметричных сильно регулярных графах // Доклады академии наук 2012, v. 311, N 2-3, 132-144.

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

34. Журтов А.Х., Махнев A.A., Нирова М.С. Об автоморфизмах 4-изорегу-лярных графов // Труды Института математики и механики 2010, т. 16, N 3, 94-102.

35. Godsil C.D., Henzel A.D. Distance-regular covers of the complete graphs //J. Comb. Theory, ser. В 1992, v. 56, 205-238.

36. Zavarnitsine A.V. Finite simple groups with narrow prime spectrum // Sibirean electr. Math. Reports 2009, v. 6, 1-12.

37. Колпакова В.А., Кондратьев A.C., Храмцов И.В. О конечных группах, имеющих несвязный граф простых чисел и композиционный фактор, изоморфный Sp4(A) // Межд. конф "Мальцевские чтения". Тез. докл. Новосибирск 2015. С. 112.