Симметричные графы и их автоморфизмы тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

ГУТНОВА Алина Казбсковна

СИММЕТРИЧНЫЕ ГРАФЫ И ИХ АВТОМОРФИЗМЫ

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации па соискание ученой степени кандидата физико-математических наук

4О&0770 Екатеринбург - 2011

1 6 июн 2011

4850770

Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН.

Научный руководитель:

доктор физико-математических наук,

профессор, чл.-корр. РАН Махнев Александр Алексеевич

Официальные оппоненты:

доктор физико-математических наук, профессор Баранский Виталий Анатольевич

кандидат физико-математических наук Ефимов Константин Сергеевич

Ведущая организация:

Южно-Уральский государственный университет

Защита состоится 5 июля 2011 года в 14.00 часов на заседании специализированного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620990, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН (г. Екатеринбург, ул. С. Ковалевской, 16).

Автореферат разослан 5 июня 2011 года

Ученый секретарь диссертационного совета, кандидат физ.-маг. наук

И.Н. Белоусов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

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

Пусть С — транзитивная группа подстановок на множестве П. Если стабилизатор Са точки а € Г2, имеет г орбит на то говорят, что С имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {а}, Д(а), Г(а). Если |Д(а)| ф |Г(а)|, то по группе С можно построить сильно регулярный граф Г, множество вершин которого Г2 и две вершины а, Ь смежны в Г, если Ь е Г(п) [7]. Д. Хигман ([7]-[11]) развил теорию групп ранга 3. Такие графы являются дистанционно транзитивными графами диаметра 2.

В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.

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

Граф Г называется регулярным графол1 степени к, если [а] содержит точно к вершин для любой вершины а из Г. Граф Г называется реберно регулярным графом с параметрами (у, к. Л), если Г содержит V вершин, является регулярным степени к, и каждое ребро графа Г лежит точно в А треугольниках. Граф Г называется вполне регулярным графом с параметрами (V. к, Л, /х), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь]

содержит ß вершин в случае d(a, b) = 2. Сильно регулярным графом с параметрами (v. к, А. ц) называется реберно регулярный граф с параметрами (v.k.X), в котором любые две несмежные вершины и, w € Г имеют ровно ß общих соседей.

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

Если вершины и, w находятся на расстоянии г в Г, то через ¿¿(u. w) (через Cj(u,w)) обозначим число вершин в пересечении подграфа Tj+i(u) (rj_i(u)) с T{w). Заметим, что в реберно регулярном графе число b\{u.w) не зависит от выбора смежных вершин и,w и равно &i = к — А — 1. Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {6о: i>i, • • • ■ bd-ii ci- ■ ■ ■, Cd}, если значения bj(u,w) и сДи,ги) не зависят от выбора вершин и, w на расстоянии г в Г для любого i = 0,.... d.

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

Через ,...,,„„ обозначим полный многодольный граф {.Iii, • • •. Ai„} с долями Л/, порядка rrii. Если mi = ... = тп = тп, то указанный граф обозначается Ä"7ixm.

Система инцидентности с множеством точек Р и множеством прямых С называется а-частичной геометрией порядка (s,t), если каждая прямая содержит ровно s + 1 точек, каждая точка лежит ровно на t + 1 прямой, любые две точки лежат не более чем на одной прямой и для любого антифлага (о, L) 6 (Р, С) найдется точно а прямых, проходящих через а и пересекающих L (обозначение pGa(s. t) или pGa). В случае а = 1 геометрия называется обобщенным четырехугольником и обозначается GQ(s%t). Точечный граф геометрии определяется на множестве точек Р и две точки смежны, если они лежат на прямой. Точечный граф геометрииpGa(s, t) сильно регулярен cv = (s + l)(l + sf/a)> к = s(£ + l)> ^ = s —l+f(a —1), ц = n(t + 1). Сильно регулярный граф с такими параметрами па-

зывается пссвОогсометрическим графом для pGa(s,t) или псевдо pGn(s. ¿)-графом.

A.A. Махневым предложена программа классификации связных вполне регулярных графов, в которых окрестности вершин изоморфны сильно регулярному графу Д с собственным значением 2. Эта программа основана на получении границы для диаметра таких графов с помощью теоремы Смита (см. теорему 3.2.5 [12]).

Цель диссертации. Целью данной работы является решение следующих задач (в рамках указанной ппрограммы):

1. Провести редукцию классификации вполне регулярных графов, у которых окрестности вершин — псевдогеометрические графы для pGs-2{s,t) к локально псевдо GQ{3,3)- и псевдо GQ(3,5)-графам.

2. Изучить вполне регулярные локально псевдо(3(5(3. 3)- и псевдо GQ(3, 5)-графы.

3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (245,64,18,16).

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

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

1. Доказано, что диаметр графа, в котором окрестности вершин — псевдогеометрические графы для pGs~2(s, £), не больше 4.

2. Определены возможные параметры вполне регулярных графов, в которых окрестности вершин — псевдогеометрические графы для pGs-2(sJ).

3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г е параметрами (245,64, 18,16).

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

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

Апробация работы. Основные результаты работы докладывались на: Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на международной конференции "Мальцевские чтения" (Новосибирск, 2010 г.), на VIII международной школе-конференции по теории групп (Нальчик, 2010 г.) и на 42-й Всероссийской молодежной конференции "Современные проблемы математики"(Екатеринбург, 2011 г.). Результаты работы докладывались и обсуждались на алгебраическом семинаре ИММ УрО РАН.

Публикации. Основные результаты диссертации опубликованы в работах [13]—[20]. Статьи [14], [16], [19] опубликованы в журналах из списка ВАК. Работы [13]—[ 19] выполнены в нераздельном соавторстве с A.A. Махневым.

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

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются вполне регулярные графы, в которых окрестности вершин являются псевдогеометрическими графами для pGs-2(s, t). Во второй главе проводится классификация локально псевдо GQ(3, 3)-графов. В третьей главе проводится классификация локально псевдо GQ(3, 5)-графов. В четвертой главе работы определяются возможные автоморфизмы сильно регулярного графа Г с параметрами (245,64,18,16).

Результаты диссертации.

Пусть Г — связный граф, в котором окрестности вершин являются псевдогеометрическими графами для pGa-\(s.f). Тогда Г — дополнительный граф для графа Зейделя и (s — l)(f + 2) делит s(s + l)(i + 1). Эта ситуация исследована в [1].

Пусть связный граф Г является локально ^-графом, где Т состоит из точечных графов геометрий рСа. По связности графа порядок (эЛ) не зависит от выбора точки и такой граф обозначается как ЕрСа(з. I).

Если Г — псевдогеометрический граф для частичной геометрии рСа(з, ¿), то он имеет собственные значения к, г — в —а, я = — (1 + <) кратностсй 1, / = +1)<(£ + 1))/(а(в + < + 1 — а)), д = (в(в — а + 1)($£ + а))/(а(8-И + 1 — а)) соответственно. В частности, псевдогсо-метрический граф частичной геометрии рС6_2(в. ¿) имеет собственное значение 2. Сильно регулярные графы с собственным значением 2 и некоторые их расширения были изучены в работе [3]. Следующие результаты являются основными в главе I.

Предложение 1 Пусть Г — связный граф, в котором окрестности вершин — псевдогеометрические графы длярвц-.2(5, О- Тогда либо диаметр Г не больше 3, либо ( = 1 « Г - граф Джонсона 7(8.4).

Теорема 1 Пусть Г является связным вполне регулярным графом, в котором окрестности вершин являются псевдогеометрическими графами длярСц-2(5,£)• Тогда выполняется одно из следующих утверждений:

1) диаметр Г равен 2, и Г имеет параметры (176,40.12,8), (245, 64.18,16), (210. 95,40,45), (27,16.10,8), (35,16,6,8), (275,112, ' 30, 56) или (1735,1470,1157,1260);

2) диаметр Г равен 3, и либо з = 3, либо в — 4 и Г — граф Тэйлора;

3) диаметр Г равен I и Г — граф Джонсона 7(8,4).

В лемме 7 из [14] было доказано, что з < 6 и при в = 3 либо ( = 1 и Г ~ граф Джонсона J(8,4), либо f 6 {3, 5}, либо Ь = 9 и Г — граф Маклафлина. Далее, в леммах 8-10 было показано, что при в = 4 граф Г является графом Тэйлора, а при в = 5, в = 6 графы не существуют.

Во второй главе работы проводится классификация вполне регулярных локально псевдо 3,3)-графов, оставшихся нерассмотренными в работе [14].

Основным результатом второй главы является

Теорема 2 Пусть Г является связным вполне регулярным графом, в котором окрестности вершин являются псевдогеометрическими графами dA&GQ(3,3). Тогда выполняется одно из следующих утверждений:

1) диаметр Г равен 2, и Г имеет параметры (176.40,12,8) или (95,40.12,20);

2) диаметр Г равен 3, и либо ц = 10 и |Г| = 151, либо (i = 12 и |Г| = 133.

В третьей главе работы проводится классификация вполне регулярных локально псевдо GQ{3,5)-графов.

Теорема 3 Пусть Г является связным вполне регулярным графом, в котором окрестности вершин являются псевдогеометрическими графами для GQ(3,5). Тогда верно одно из утверждений:

1) диаметр Г равен 2, Г имеет параметры (245, 64,18.16) и собственные значения 8. —6 кратностей 100,144;

2) диаметр Г равен 3, = |Г;(я)| для некоторой вершины а и либо

(?) р = 20, k2 = 144 и kz < 4, либо (ii) ß = 18, fc2 = 160 и 2 < k3 < 5.

В теоремах из второй и третьей глав были упомянуты графы с параметрами (176, 40.12, 8), (95, 40.12, 20) и (245,64,18.16). Автоморфизмы сильно регулярного графа с параметрами (95,40,12, 20) были изучены в работе [2].

В четвертой главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (245.64,18,16).

Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов сильно регулярных графов Г. Хигман предложил оригинальный метод, использующий теорию характеров конечных групп. Этот метод изложен в монографии П. Камерона [6]. При этом графу Г отвечает симметричная схема отношений (X, {Rq, .... R2}),

где X — множество вершин графа, Дц — отношение равенства па X, — отношение смежности в Г, /?2 ~~ отношение смежности в дополнительном графе Г. Если Р и С} — первая и вторая матрицы собственных значений схемы, то

Р =

1 1 1 к г в

■к-1 -г - 1 -в - 1

РЯ = (}Р = VI. Здесь V — число вершин, к, г, в — собственные значения графа Г кратностей 1, /, V — / — 1 соответственно (указанные кратности образуют первый столбец матрицы С}).

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

прямой суммой собственных Ф(С)- инвариантных подпространств И'о ® И"! © матрицы смежности графа Г. Пусть ~ характер представления ф\\\- Тогда, для любого д 6 С получим

2

где а]{д) — число точек х из X таких, что (х, х9) £ Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть равенства для ХгЫ — число рациональное, то хАэ) ~ целое число.

В данной работе этот метод применяется для изучения автоморфизмов гипотетического сильно регулярного графа с параметрами (245,64.18,16).

Основным результатом четвертой главы является следующая теорема.

Теорема 4 Пусть Г — сильно регулярный граф с параметралш (245,64,18,16), д — элемент простого порядка р из Аи1;(Г) и = Р1х(д). Тогда верно одно из утверждений:

(1) — пустой граф и р = 5 и сс\(д) делится на 70 или р = 7 и а\(д) делится на 98;

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

(?) п = 5, р = 3, «1(5) = 42г + 12 или р = 5, Qi(g) = 70s — 30,

либо

(ii) тг = 8, р = 3 и а\(д) = 42г - 6, либо

(iii) п. = 10, р = 5 и ai(g) — 70s + 10;

(iv) п = 11, р = 3 и = 42г + 18;

(3) является т-кокликой, р = 2, т. нечетно, 5 < т < 21 и tti(ff) ~ 8т делится на 14;

(4) П содержит геодезический 2-пугпь и либо

(г) р = 7, |П| = 7г, 5 < г < 11 и ai((?)/14 + Зг делится на 7,

либо

(ii) р = 5, = 5s, 4 < s < 15 и а\(д)/Ъ + s делится на 14;

(iii) р = 3, = 3t + 2, ai(g) — 6w u3t + 2 + w делится на 7; (гг;) р = 2, |П| = 21 + 1, 2 < I < 38, Qi(g) = 2w и число

(61 + 3 + w)/7 нечетно.

Автор выражает глубокую благодарность своему научному руководителю профессору А.А.Махневу за постановку задачи, внимание и поддержку, а также всем участникам семинара отдела алгебры и топологии ИММ УрО РАН за критические замечания и плодотворное обсуждение результатов диссертации.

Список литературы

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

[2] Махнев, A.A. Об автоморфизмах сильно регулярного графа с параметрами (95,40,12,20) / A.A. Махнев, Н.В. Чуксина// Владикавказский матем. журнал - 2009.- Т11,- N4.- С. 44-58.

[3] Кабанов, В.В. О сильно регулярных графах с собственным значением 2 и их расширениях / В.В. Кабанов, A.A. Махнев, Д.В.

Падучих// Доклады Академии паук - 2010.- Т.431,- N5.- С. 583586.

[4] Buekenhout, F. Foundations of incidence geometry / F. Buckenhout//' Handbook of incidcnce geometry: buildings and foundations/ F. Buekenhout. - Elsever Science. Amsterdam.- 1995.-P. 63-107.

[5] Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.

[6] Cameron, P. Permutation Groups/ P. Cameron.- London Math. Soc. Student Texts 45.: Cambridge Univ. Press, 1999.

[7] Higman, D.G. Finite permutation groups of rank 3/ D.G. Higman // Math. Z.- 1964,- Vol.86.- P. 145-156.

[8] Higman, D.G. Primitive rank 3 groups with a prime subdegree/ D.G. Higman // Math. Z.- 1966,- Vol.91.- P. 70-86.

[9] Higman, D.G. Intersection matricics for finite permutation groups/ D.G. Higman // J. Algebra.- 1967,- Vol.6.- P. 22-42.

[10] Higman, D.G. On finite affine planes of rank 3/ D.G. Higman // Math. Z.- 1968,- Vol.104.- P. 147-149.

[11] Higman, D.G. A survey of some questions and resalts about rank 3 permutation groups/ D.G. Higman // Actes, Congres Int. Math. Rome.- 1970,- Vol.1.- P.361-365.

[12] Brouwer, A.E. Distance-regular graphs/' A.E. Brouwer, A.M. Cohen, A. Ncumaier /'/' Berlin etc: Springer-Verlag.- 1989.- 495 p.

Работы автора по теме диссертации

[13] Гутнова, А.К. О графах, в которых окрестности вершин являются псевдогеометрическими графами для pG6._2(s, t) /' А.К. Гутиова, А.А. Махнев /'/' Алгебра и ее приложения. Труды межд. копф., посвященной 80-летию со дня рождения А.И. Ко-стрикина. К Б ГУ: Нальчик.- 2009. С.38-42.

[14] Гутнова, A.K. О графах, в которых окрестности вершин являются псевдогеомстрическими графами для pGs_2(s. t) / A.K. Гутнова, A.A. Махнев // Доклады академии наук 2010, т. 431, N 3, С. 300-304.

[15] Гутнова, А.К. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3, 3) / A.K. Гутнова, A.A. Махнев // Тезисы международной конференции "Мальцевские чтения". посвященной 70-летию академика Ю.Л.Ершова, Новосибирск 2010, С. 72.

[16] Гутпова, А.К. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3, 3) / A.K. Гутнова, A.A. Махнев /'/' Доклады академии наук 2010, т. 433, N 6, С. 727-730.

[17] Гутнова, А.К. Графы, в которых окрестности вершин — псевдо-гсометрические графы для GQ(3,5) / A.K. Гутнова, A.A. Махнев /7 Теория групп и ее приложения. Труды восьмой Международной школы-конференции но теории групп, посвященной 75-летию со дня рождения В.А. Белоногова. КБГУ: Нальчик 2010, С. 70-76.

[18] Гутнова, А.К. Об автоморфизмах сильно регулярного графа с параметрами (245. 64,18.16) / А.К. Гутнова, А. А.Махнев // Труды 42-й Всероссийской молодежной конференции "Современные проблемы математики". Екатеринбург 2011, С.195-197.

[19] Гутнова, А.К. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3,5) / A.K. Гутнова, A.A. Махнев /7 Доклады академии наук 2011, т. 438, N 5, С.595-598.

[20] Гутнова А.К. Об автоморфизмах сильно регулярного графа с параметрами (245. 64.18,16) / А.К. Гутпова // Сибирские электронные матем. известия - 2011.- Т. 8,- С.4 18.

Введение

1 О графах, в которых окрестности вершин являются псевдогеометрическими графами для рС«,-2(3, £)

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

1.2 Сильно регулярный случай.

1.3 Графы диаметра 3, в которых окрестности вершин изоморфны

2 Графы, в которых окрестности вершин — псевдогеометрические графы для 3,3)

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

2.2 Локально псевдо С<5(3,3)-графы.

3 Графы, в которых окрестности вершин — псевдогеометрические графы для 3, 5)

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

3.2 Локально псевдо 3, 5)-графы.

3.3 Случай ¡1 =

3.4 Случай /х =

4 Автоморфизмы графа с параметрами (245,64,18,16)

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

4.2 Автоморфизмы графа с параметрами (245, 64,18,16)

4.3 Автоморфизмы малых порядков.

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

Пусть С — транзитивная группа подстановок на множестве Если стабилизатор точки р £ П, имеет г орбит на П, то говорят, что С имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}, А(р), Г(р). Тогда по группе С удастся построить сильно регулярный граф Г, множество вершин которого О и две вершины р, д смежны в Г, если <7 е г(р) [17].

Д. Хигмеи ([17]-[21]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.

В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.

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

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

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

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

Граф Г называется вполне регулярным графом с параметрами (у, к, А,/и), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь] содержит 11 вершин в случае й{а, Ъ) = 2. Сильно регулярным графом с параметрами (у, к, А, ц) называется реберно регулярный граф с параметрами (у, к, Л), в котором любые две несмежные вершины и,и) Е Г имеют ровно ¡1 общих соседей.

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

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

Если вершины и, и) находятся на расстоянии г в Г, то через ¿»¿(гл, т) (через Сг(и, и))) обозначим число вершин в пересечении Гг+1(и) (Гг1(^)) с Г(ги). Заметим, что в реберно регулярном графе число Ъ\{и,и)) не зависит от выбора смежных вершин и, У) и обозначается через б^Граф Г диаметра 6, называется дистанционно регулярным с массивом пересечений {&о, 2>1,., Ьс1-и С1,., Ог}, если значения Ь((и, ги) и сг-(п, гу) не зависят от выбора вершин и, w на расстоянии г в Г для любого г — 0,., d.

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

Через -Кть.,тп обозначим полный многодольный граф {Mi,., Мп} с долями Mi порядка rrii. Если mi = . - - = тпп = тп, то указанный граф обозначается Кп ХШ'

Система инцидентности с множеством точек Р и множеством прямых С называется а-частичной геометрией порядка (s,t), если каждая прямая содержит ровно s +1 точек, каждая точка лежит ровно на t + 1 прямой, любые две точки лежат не более чем на одной прямой и для любого антифлага (а, L) G (Р, С) найдется точно а прямых, проходящих через а и пересекающих L (обозначение pGa(s,t) или pGa). В случае а = 1 геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Точечный граф геометрии определяется на множестве точек Р и две точки смежны, если они лежат на прямой. Точечный граф геометрии pGa(s,t) сильно регулярен с v = (s + 1)(14-st/а), k — s(t+ 1), Л = s — 1 -\-t(a — a(t + 1). Сильно регулярный граф с такими параметрами называется псевдогеометрическим графюлi для pGa(s,t) или псевдо pGa(s, ¿)-графом.

A.A. Махневым предложена программа классификации связных вполне регулярных графов, в которых окрестности вершин изоморфны сильно регулярному графу А с собственным значением 2. Эта программа основана на получении границы для диаметра таких графов с помощью теоремы Смита (см. теорему 3.2.5 [16]).

Цель диссертации. Целью данной работы является решение следующих задач:

1. Провести редукцию классификации вполне регулярных графов, у которых окрестности вершин - псевдогеометрические графы для к локально псевдо (7(2(3, 3)- и С(5(3, 5)-графам.

2. Изучить вполне регулярные локально псевдо (?<3(3, 3) и 5)-графы.

3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (245,64,18,16).

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

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

1. Получена граница для диаметра графов, у которых окрестности вершин - псевдо геометрические графы для рС8-2(3^).

2. Получены возможные параметры вполне регулярных графов, у которых окрестности вершин - псевдогеометрические графы для 2(5, в случаях, когда диаметр графа равен 2, 3 или 4.

3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (245,64,18,16).

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

Апробация работы. Основные результаты работы докладывались: на Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на международной конференции "Мальцевские чтения"(Новосибирск, 2010 г.), на VIII международной школе-конференции по теории групп (Нальчик, 2010 г.) и на 42-й Всероссийской молодежной конференции "Современные проблемы математики" (Екатеринбург, 2011 г.).

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

Публикации. Основные результаты диссертации опубликованы в работах [23]—[30]. Работы [23]—[29] выполнены в нераздельном соавторстве с A.A. Мах-невым.

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

1. Buekenhout, F. Locally polar spaccs and related rank 3 groups /' F. Buekenhout, X. Hubaut// J. Algebra 1977, v. 45. P.391-434.

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

3. Cameron, P.J. Permutation Groups/ P.J. Cameron// London Math. Soc. Student Texts 45, Cambridge Univ. Press. 1999.

4. Hobart, S.A. EpGs with minimal II/ S.A. Hobart, D.R. Hughes// Geom. Dedic. 1992, v. 42, P.129-138.

5. Hobart, S.A. Extended partial geometries: nets and dual nets/ S.A. Hobart, D.R. Hughes// Europ. J. Comb. 1990, v. 11, P.357-372.

6. Махнев, А.А. О графах, в которых окрестности вершин являются графами, дополнительными к графу Зейделя/ M.JI. Карданова, А.А. Махнев// Дискр. матем. 2009, т. 3, N 3, С.71-83.

7. Neumaier, A. Strongly regular graphs with smallest eigenvalue — m/ A. Neumaier// Arch. Math. 1979, v. 33, P.392-400.

8. Махнев, A.A. О расширениях частичных геометрий, содержащих малые ¡л-подграфы/ А.А. Махнев// Дискр. анализ и исслед. операций 1996, т. 3, N 3, С.71-83.

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

10. Brouwer, A.E. Distance-Regular Graphs/ A.E. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag 1989, 495 p.

11. Haemers, W. The pseudo-geometric graphs for generalized quadrangles of order (3,t)/ W. Haemers, E. Spence// Eur. J. Comb. 2001, v. 22, N 6, P.839-845.

12. Behbahani, M. Strongly regular graphs with nontrivial automorphisms/ M. Behbahani, C. Lam// Discrete Math. 2011, v. 311, P.132-144.

13. Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.

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

15. Higman, D.G. Finite permutation groups of rank 3/ D.G. Higman// Math. Z.- 1964.- Vol.86.- P.145-156.

16. Higman, D.G. Primitive rank 3 groups with a prime subdegrce/ D.G. Higman/'/ Math. Z.- 1966.- Vol.91.- P.70-86.

17. Higman, D.G. Intersection matrices for finite permutation groups/' D.G. Higman// J. Algebra.- 1967.- Vol.6.- P.22-42.

18. Higman, D.G. On finite affine planes of rank 3/ D.G. Higman// Math. Z-1968,- Vol.104.- P. 147-149.

19. Higman, D.G. A survey of some questions and results about rank 3 permutation groups/ D.G. Higman// Actes, Cjngres Int. Math. Rome 1970.-Vol.l.- P.361-365.

20. Кабанов, B.B. О сильно регулярных графах с собственным значением 2 и их расширениях/ В.В. Кабанов, A.A. Махнев, Д.В. Падучих// Доклады Академии наук 2010.- Т.431. - N5, апрель. С.583-586.Работы автора по теме диссертации

21. Гутнова, А.К. О графах, в которых окрестности вершин являются псевдогеометрическими графами для pGs-2(s, t) / А.К. Гутнова, A.A. Махнев // Доклады Академии наук 2010, т. 431, N 3, С.300-304.

22. Гутнова, А.К. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3,3) / А.К. Гутнова, A.A. Махнев // Тезисы международной конференции "Мальцевские чтения", посвященной 70-летию академика Ю.Л.Ершова, Новосибирск 2010, С.72.

23. Гутнова, A.K. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ{3, 3) / A.K. Гутнова, A.A. Махнев // Доклады Академии наук 2010, т. 433, N 6, С.727-730.

24. Гутнова, А.К. Об автоморфизмах сильно регулярного графа с параметрами (245,64,18,16) / А.К. Гутнова, А.А.Махнев // Труды 42-й Всероссийской молодежной конференции "Современные проблемы математики". Екатеринбург 2011, С.195-197.

25. Гутнова, А.К. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3,5) / А.К. Гутнова, A.A. Махнев // Доклады Академии наук 2011, т. 438, N 5, С.595-598.

26. Гутнова А.К. Об автоморфизмах сильно регулярного графа с параметрами (245,64,18,16) / А.К. Гутнова // Сибирские электронные матем. известия,- 2011.- Т. 8.- С.4-18.