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

Нл пранах рукописи

Нирова Марина Сефовна

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

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

АВТОРЕФЕРАТ

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

Екачериибург - 2007

003071769

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

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

доктор физико-математических наук, член-корр РАН МАХНЕВ Александр Алексеевич

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

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

кандидат физико-математических наук НОСОВ Виталий Валерьевич

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

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

Защита состоится 26 июня 2007 г в 14 часов на заседании диссертационного совета Д 004 006 03 в Институте математики и механики УрО РАН по адресу

620219, г Екатеринбург, ул С Ковалевской, 16

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

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

В В Кабанов

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

Актуальность темы В спя»! с -завершением классификации коночных проси,IX rpvnn поникла задача единого представления конечных нро-{'П.IX ipyrrn Персиек пивным направлением являемся поиск шкого класса конечных [еометрпи, что каждая конечная простая группа действует флаг-ipaiun i шшо па иекотрон i еомечрии и ве о кюмеч'рии л oí о ктака допускаг ют классификацию [1 3] Например, клае с билдиш он Тик а характера syei группы Лиечзского тина [4| Позднее в ном панрав ícimn по ¡никли задачи, не связанные с ipynnoni.iu действием, в частности, такой является задача класс ификации дистанционно регулярных графом [5|

Cieneimto нерпшны называется число вершин в се окрестности Граф Г называемся регулярны и степени если степень любой вершины а 1рафа Г равна к Граф Г назовем рьбцто регулярным с параметрами (v,k, А), если он содержи! v вершин речулнреи с ичюни к и каждое его ребро аЬ нежит в А треугольниках Граф Г — вполне регулярный граф с параметрами (г), А,, А, /х), если ои реберио регулярен с- с осп пси нз>юпшми параметрами и [а] П [6] (одержит р, вершин для любых двух вершин а,Ь, находящихся на расстоянии 2 в Г Вполне регулярный граф на зывается сильно регулярным графом, если он имеет диаметр 2

Пусть G трапзиишная группа нодиановок на множестве П Если подгруппа Gp группы G, с ос тоящая из всех поде ганонок фиксирующих iomkj а е Q имеет г орбш то говорят, что G является группой рант г Пусчь г = 3 и сооi пет ст вуюшне 3 орбиты — зто {а}, Г(а), Д(а) Тогда по группе G можно пек троить сильно регулярный граф Г множес riso вершин которого — Пи две вершины р, q смежны г. Г, если р G Г(д) [С|

ДХигмэп [G 10| развил icoi>iho групп ранга 3 Эти 1рунны являются группами авшморфизчов сильно регулярных графов, т е дне ынциоиио i ран зи i ивных графой диамемра 2

Граф Г диаметра d называемся дистанционно фапзшииным если для любого г € {0, ,d} и для любых вершин u,v,x,y с условиями d{u,v) =

</(х,у) = г, оуществует автоморфи зм д графа Г такой что (ив, V9) = (х, у) Дистанционно тратит шшые /рафы диаметра 2 (графы ранга 3) сыграли важную роль п классификации конечных простых групп Более нотовипы (гюрадических групп имеют представления в виде групп автоморфизмов графов ранга 3 |11|

Если вершины и,ги находятся на расстоянии г в Г, го через Ьг(а,т) (через сг(и,ги)) обозначим число верпшп в персчечешш Гг+1(и) (в пересечении Г,_1(и)) с [ад] Дистанционно регулярным зрафом называется граф диаметра й н котором дня любою г € {0,1, параметры -ш) и сг(и,ги) не зависят от выбора першин и, ги, а зависят юлько 01 расс юяния межд\ этими вершинами в графе Г

Ярким примером перехода ог изучения зруиновых симмегрий к комбинаторным является расширение класса дииапцпонно трапзшивпых гра-с]ю» до класса дислапцпогшо регутярных трастов В настоящее время при исследовании 1рафов и конечных геоморий вовлекаются симметрии все более общего вида

Пос кольну каждый дистанционно регулярный грае}) является вполне ре-Iулярпым графом (в часгпос гн, реберно регулярным графом), то некем о-рые рс зульта гы об этих класс ах графов могут бы 1 ь ис пользованы и т еорни дистанционно ресутярпыч Графов

Если Г неполный связный реберно регулярный грае}) с параметрами (у, к, А) то параметр Ь](и,и;) не зависят от выбора смежных вершин и, гу и верно равеис гво Ь\ = к — X — 1

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

Через Кт1> ,„г„ обозначим полный п-дольный граф с долями порядков тх, ,тп Если т\ = . = тп = т, то соответствующий грае}) обозпа-

мае и я мерс"! КпХт Граф Кг,т наливается т-лапай Треугольным графой Т(тп) называема граф с множест вом неупорядоченных нар из X ii качение вершин |Х| = гп и пары {а, ?;}. {с, <1} смежны toi да и только тогда, кемда они имею! едипс и>енпый общий -элемент Граф на множестве вер-ниш А' х Y иашваекя m х п решетъой, если |Х| = т, |У| = п и »ер-шины {х\,у\), (22,2/2) смежны 101дл н только тогда, когда х-[ — Х2 или 2/1 = 2/2 Графом Джонсона J(n,m) называется грае]), вершинауш которого являюкя т-зломеи шые нодмножос им дапнот п-элемент нот множества причем дне вершины а, Ъ с межны юлько если \а П = m — 1 Граф П+-ли P{q) н качестве вертим имеет плементы поля Fq q = 1 (mod 4) и две1 вершины а,Ъ смежны только если Ъ — а является ненулевым квадратом в Fg Грас}> Пеюрсена — это дополнительный граф для треугольного графа Т(5) (oír имеет параметры (10 3,0 1)) Граф Клебша (Шлефли) — это единственный сильно регулярный граф с; параметрами (1G,1(),G,G) (с параметрами (27,10,10,8)) Граф Шрикхандо — это едипс твеппый стыыю регулярный локально шее тиуюльный 1раф с параметрами (16 0,2 2) Имеется точно 3 сильно регулярных графа, имеющих нарамефы графа Т(8), по не изоморфных Т(8) Эги графы называются графами Чата Графом Хофмаиа-Синг пиона называется едипс шейный с ильно peí улярный грае}) с параметрами (50,7,0 1) Графом Хчгмегш-Симеа называется единс гнойный елмыю регулярным 1рдф о параметрами (100,22,0 G)

Чштичпои геометрией pGa(s,t) называется система инцидентности, состоящая in юмек и прямых в ко юрой каждая прямая содержит s + 1 точку, каждая точка ложи г на t + 1 прямой (дно прямые порос екают ся по более, мом но одной i очко) и для любой точки а по лежащей на прямой L, найдется ючно а прямых проходящих мороз а п пересекающих L Если а = 1, то i еомотрия называется обобщенным четыре ¡угольником и обо-шачасия GQ(s,t) Если а = £, то геометрия на ¡ываетея сетью Точечным графом частичной юомотрии называется rpac¡>, вершинами которою являются топки геометрии и две: раишчные вершины смежны, если они лежа г на одной прямой Легко понять, что точечный граф частичной геометрии

pGa(s,t) сильно регулярен с параметрами i> = (s+l)(l+si/a), к = s(£ + l), Л = (s — 1) + (а — 1)£ ¡1 = a(t +1) Любой сильно регулярный граф ( такими параметрами дли некоторых a,s,t называется п< елёпгсоки mpuvccKti и графом дляpGa(s,t)

Частичным четыретугольником PQ(s,t,fi) напивается спсчема инцидентности, состоящая и! точек и прямых, и которой каждая прямая содержит 5 + 1 точку, каждая точка лежит па t + 1 прямой (дне прямые пересекаются не более, чем по одной точке) и дчя любых днух несмежных точек пересечение их окрестное гей п точечном графе является /ькокликой Точечный граф частичного четырехугольника PQ(s, t, /î) сильно регулярен с параметрами v = 1 + s(t 4- 1) + s2f(t + 1)/// k = s(t + 1) и A = s — 1 Частичный четырехут ольпик назовем узким, если t < 6

Цель работы. В диссертации ис следовани впотпе регутярпые графы с; малыми Ъ1, класс ифпцирошшы узкие часличиые четырехугольники и определены порядки и подграфы неподвижных точек их автоморфизмов а также изучены у-однородные расширения частичных геометрий pGa(s,t) для ¡р G {s, s — 1}

Методика исследования Основными методами исследования являются теоретико-графовые методы, используются также методы теории конечных групп и теория представлений конечных гр>пи (метод Г Хит мена) Научная новизна. Все основные результаты диссертации являются новыми Найдены параметры сильно регулярных графов с < 18 получено описание вполне регулярных графов с &i < 5, классифицированы s-однородгтые и сильно (s — 1)-одиородные расширения час шчпых тео-метрнй pGa(s,t), доказано, чго сильно регулярный граф с; параметрами (400 21,2,1) не является верппшпо тран зинизшим

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

Апробация работы. Резулыаты работы докладывались па Международной алгебраической конференции, посвященной 70-легию Л II Шенри-

6

на (Екак'ринбург, 2005), па Международных конференциях "Мальцеве кие 1п опия "(Новосибирск, 2003 н 2000) на Международной школе-конференции по теории групп, посвященной 73-летию со дня рожденя А И Старостина (Пршльбрусье 2006), на 37-й и 38-й Рем иопальпых молодежных конференциях ИММ УрО PAII, на алгебраических семинарах Института математики н механики УрО РАН

Публикации. Основные результаты опубликованы в рабоых [19-24| Рабоп.г [19 23] наппеаны в нераздельном соавторстве с Махневьш А А

Структура и объем диссертации. Диссертация состоит и ¡ введения i рех глав и списка ли i ера i уры (42 наименования)

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обсуждается история вопроса, даются определения н формулируются основные результаты рабогы

В главе 1 рассматриваются i рафы с малыми значениями Ъ\ Пуоь Г реберно регулярный граф с параметрами (v, к, А) Тогда cienenr. вершины в любом ¿i-подграфе и i Г не болтано к—2bi Позгом\ для ц, = к—2Ъ\ + 1 и любых вершин u,w, находящихся на расстоянии 2 выполняется даравеиспзо ц(и,ги) > /г, Пару вершин (u,w), находящиеся на расстоянии 2, назовем хорошей сели ¡.i(u,w) = ¿í,. назовем почти 'uipouieú счыи fi(u,w) = fit +1 Для w,z € ^(u) тройку вершин назовем юрошеи если fi(u,w) + ц{и,г) < 2к — 4bt + 3, назовем почти юртш ú, если fi(u,w) + /х(и, z) = 2к — АЪ\ -f 4 Псарные резулыаты о x0j)0innx парах получены и [12], где, в частности, установлено, чю иерсчечеиие окреч гиосчсй вершин хорошей тройки содержи! не более одной вершимы

При изучении реберно рсч улярных трастов полезным являемся описание ночш хороших 1])оек Следующий резулыат occ)6einio поте ¡en при изуче-нни |рафов диамечра большею 2

Теорема 1. Пусть Г (вя.неыи реберно регулярный граф с параметрами (v,k, A), bi = к — А — 1 и к > 3bi — 3 Если троЛьа (u,w,z) является почти wpouicit и [w] П [z] — [и] содержит вершину у несмежную

7

с вершина ми из А = [tí] П [w] П [z], то либо |Д| < 2 либо |Д| = 3 и 0>\,к) € {(5,12), (6,15), (6,17)

Замечание Е< ли Г граф Шлефцп d(u, w) = 2, то /¿ = к—2Ь\+2 [и]П [«;] являекя полным мпогодольным графом " Для любой вершины z £ [w] — [м] подграф [и] П [w] П [z] является 4-кликой Но в -ном графе каждая вершина и з [w] П [z] — [w] смежна с некоторой вершиной и з [w] П [ги] П [л]

Изучение реберио регулярных графов даже в случае h = 5 идет с большим трудом Однако для t ильно регулярных графов с итуацня гораздо проще

Сильно рпулярные графы с собственным значением —2 были классифицированы Зейделем Любой зейделев граф это либо полный \inoi о-демьпый грае}) КГх2, либо решетчатый или треугольный |рнф либо один из графов Шрикчапде, Чаши, Петере епп Клебша или Шлефлп

Теорема 2 Пугть Г — сильно регулярный граф с 0 < Ь\ < 18 Тогда Г является одним ui следующиг графов

(1) граф с параметрами (4bi -f l,2bi,bi — l,í>i), 2>i ф 5,8,14,17 или потый ипогодольныи граф Кгх(ь1+\),

(2) зейделев гриф или его дополт une,

(3) пи вдогеометричесъиИ грпф для GQ(s,t), {s,í} = {2, 2}, {2,4}, {3, 3}, {3,5} л ni его dono пи en ne,

(4) псевдогсоме.туичсскии граф) дли сети pGt(s,t). где либо t = 2, s = 4,5,6,7,8 или 9 либо t = 3, 5 = 4,5,6 или 7,

(5) пссадогеометрический граф д и pG¿(5,2), pG3(6,2) р£?4(7,2), pG^(8,2), PG3(9,2), pGi{7,3), pG4(8,3), pG5(9,3) PG6(8,5), pG8(15,2), PGn{ 16,3), pG'15(19,3) unupGwi24,3),

(6) допотигпельныà граф) либо к графу из пуиътов (4) или (5) либо к гкевдогео wmpuvei кому г]>афу для pG2(4,7) или pG$(5, 7),

(7) графе параметрами (49,32,21,20) (50,7,0,1) (56,10,0,2), (77,16,0,4), (85,14,3,2), (99,14,1,2), или, (126,25,8,4),

(8) дополнитегьиыà граф либо для графа vi пункта (7), либо дтя графа

с пара метра ми (81,20,1,6) или (100,22,0,6)

Хорошо гмвес пю чго с вялгый граф с &i = 1 является многоугольником или полным многодольным графом < долями порядка2 Графы с í>i G {2,3} изучались и [13|, г рафы с bj = 5 н к > 14 класс ифицировапы и [14| а вполне регулярные графы с Ь\ = 4 опис аны и [15|

Теорема 2. Пусть Г — святы!) вполне регулярный граф с параметрами (v,k,X,fi) и bi < 5 Тогда либо Г является ионным миогод/иьным графом Knx^i+i)- регулярным графом бе i треугольников imcntuu b\ + 1 или реберным графом регулярного графа без треугольников степени Ь\ + 1 обхвата, большего 1 либо выиотяется одно tu еждующхч утверж деиий

(1) ¿i = 2 и Г является 3 х 3-рсикткст, треугольным графом Т(5) графом Петер!сна v ni графом уъ,оеим)ра

(2) b\ = 3 и Г является локально шестиугольны и графом, треугольным графом Т(6) или графюм Клебиш

(3) bj = 4 и либо

(г) диаметр Г равен 2 и Г является графом Пми с параметрами (17,8,3,4) 5x5 р< иитъой, треугепьным графом Т(7) или дополнительным графой ь 4x4 ранетке треугольному графу Т{6) или графу Ккбша, (гг) (i = 1 и Г является вполне регу шрным графюм с параметрами («,6,1,1),

(ггг) ц = 2 и Г является либо г]шфом Клейна либо 5-кубом nudo графом инцидентности с имметричтш 2-(11,5,2) еземы либо единственным вполне регулярным грифом с параметрами (20,6,1,2), (гг») // = 4 и Г является графом Джонсона J{6,3),

(5) bi = 5 и i ибо

(г) диа метр Г равен 2 и Г яв >)яс тся 6x6 реин ткои графюм Шла/) т, треугепьным графюм Т(&) или одним ui mpe-i графов Чаига

(гг) р, = 2 и Г является либо G-вилентны м ректаграфом, либо локально вое ьмиуго ¡ьным графом диаметра, не большего 4

Пример 1 Пи 11, Г граф, вершинами которого являю к л З-инклы

in еимметричеч'кой iруины ¿5, причем две вершины а, Ь смежны, если ab является ииволюниен Тогда Г является вполне регулярным графом с параметрами (20,6,1,2)

Во второй игаве работы ктасеифипироваиы улкие частичные четырехугольники и илучеиы их авюмор<|)н ¡иы

Легко поиятг., чго граф колшшеарпоети частичного четырехугольника PQ(s,t,fi) сильно регулярен с параметрами (l + s(£+l) + s2f(£+l)//t,s(i + l),s — 1,/г) Обратно если сильно регулярный грае}) не содержит индуцированных подграфов, изоморфных /ч с удаленным ребром то система инцидентности, точками которой являются вершины графа а прямыми максимальные клики графа, будет чае шчпым четырехугольником

Ясно, что с ильно регулярный граф с А < 1 или с /i = 1 явчнстся графом коллипеарнос iи частичного четырехугольника Назовем частичный четырехугольник PQ{s,t,)i) ульим еелгг £ < 6

Теорема 4 Пусть Г является графом ьоаяинсарности частичного чс-тырелугопники PQ(s,t,/.i), t < 6 Тогда выполняется одно из с асдующи i утверждении

(1) Г по тьей двудольный граф Kni„ или п X п решетка,

(2) Г граф коплитарнос mu GQ(s,t), 2 < t < 6,

(3) Г граф Петере с на, граф Хофшпш-Синглшпни допопттепышй граф д и< графа К wCnua граф < пара ш трами (99,14,1,2) или (400,21,2,1)

Группа автоморс})и змов полного двудольного rpacj>a K„t„ и rix п решетки ивляе!ся с плетением Sn с помощью группы порядка 2 Группа автоморфизмов графа Печерсепа изоморфна 5s графа Хофмапа-Сиш лтопа рас пшрению группы £/з(5) с помощью группы порядка 2 и дополнительною rpaejia для графа Клебша расширению элементарной группы порядка 1G с помощью группы S5 Строение группы авгоморс})и змов гипотетического rpaejm е параметрами (99,14,1,2) выяснено в [1С|

Теорема 5 Пусть Г является сильно регулярным графом < пара-

ли три ни (400,21,2,1), д меметп про/ того порядна р чи Аи<;(Г) и Л = Рк(д) Тогда аыпо тяет<я одно <и с аедующи I 1/тв< ржденнй

(1) Д т)! той граф п р = 5

(2) либо |Д| = 1 ир = 3 или 7, 1нбо А яп /яепн я 4-клпьпй и р = 2 пли

3,

(3) р = 2 Д (одеря< ится в а1- дгя некоторой вершины а £ Д Д(а) является оСтединением >р июгироваиныъ вершин и гр треугочышьов, при-чек, (р,-ф) = (0,7), (3,4), (2,3), (1,2), (6,1) или (5,0)

В доказательстве теоремы 4 используется мсчод Хигмепл приложения теории харакюров конечных групп к и учению но шожиых порядков и подграфов неподвижных точек аптоморфи шов дне ташшопно реп улярпых графов (см |17|)

Следствие Пу< ть Г явпяепкл г и чьно регулярными графом, г пара метрами (400,21,2,1) и О = Аи1(Г) Тогда выполня/ння одно и I ыедунпцхп утверждений

(1) 7 делит |(?| и |С| детт 2 3 7

(2) 5 де шгп |С| и |С| дгаит 10 или 3 52;

(3) \С\ делит 2 З3

В третьей главе1 дшеертции изучены ^-однородные расширения частичных юомегрпй рСа(5,с ц> = 5 и сильно ^однородные юомегрии с (р = в — 1 В час топи, полученные ранее Камероном и Фишером [18| рсчулыаты по расширениям обобщенных чем ырехугольииксж обобщаются па случаГ) частичных геометрий

Геомиприей 5 ранга 2 называется еж тема инцидентноеги {Р,В) где Р — множество точек, В — некоторый набор подмножеств и 5 Р, иашваемых блоками Две точки па шваючея коллинеарными, ее ,ти они лежат в общем блоке Пара (а, В) и? (Р,В) называется флатом, если точка а принадлежит блоку В, и аишфнатом в иренивном случае Геомория называется (^-однородной если для любою антифласа (а, В) число точек в блоке В, коллинеарпых точке а равно 0 или (р п сильно у>-одиороцной, если что

число всегда равно у?

Вычет $а геометрии в точке а это кчшетрия (Ра,Ва), где Ра множество всех точек, коллинеарпых а и Ва — {В—{а} \а € В 6 В} Пусть 3- семейспю геометрий ранга 2 п всякий вычет лежш в Т Тогда говорят что 5 является расширением Т Спяшое расширение семейства частичных геомегрий рС?а(в,£) обозначается как £рСа(5,

Пусть геометрия 5 является у-однородпой ЕрСа($, £) Если ср = в + 2, 10 5 называется одпошчечным расширением (и граф Г(<!>) является потным) Например 3-(22,6,1) схема Мап.е зго однсночечное расширение проективной плоскости РС?(2,4)

Если <р = в + 1, то геометрия 5 будет сильно (я + 1)-однородпой, и Г является полным многодольным графом К^^х^^/а) С этом случае для любой точки а множество ючек вычета <?„ имеет разбиение на в + 1 ово-идов Среди известных обобщенных четырехугольников только 0(3(8,1), ОС}{ 1,4). СЯ(2«,2°) СЯ(Ч - 1><7 + 1), вСЦд + 1,Я- 1), где 9 -

степень нросгого числа, доиускаЮ1 разбиение точечного множеств овон-дами

Пример 2. Для любого 1> 1 имеется единственная геометрия ЕСС](1,¿) Ее точечный граф является полным трехдольным трастом К^хЦ+г). а множество блоков совпадает с множеством 3-клнк -»того графа

Пример 3. Сильно ($+ 1)-однородный четырехугольник ЕСС}{$, 1) су-щеслвусч при всех в = q— 1, где с/ есть степень 2 Примеры с э = 1 и й = 3 едипечвепны |7|

Пусп> 7г — РСГ(2,д) а г очка в 7Г, С гиперовал, содержащий а а Т обозначает группу (порядка (р) всех маний с цепIром и точке а Точками ЕйС} являются все точки 7Г, отличные ог а, блоками являюня прямые не содержащие а и трансляции прямой С — {Р} под действием 1руппы Т

Примеры (« + 1)-одпорс)дпых ЕСС,~)(ч ~ 1,<7 +1) Л'!Я Ч — 2П построены А Пасшш и Д Пасечником

Теорема б Пусть 5 яв/ииппи 1 э-о&чорпдпой геоиетриеи ЕрСа(зп

Г дополнение h Г(<5) Тогда либо s = 2 (и геометрия S чиве/ гпиа), либо S есть EpGi^s, 1), Г является (и гьно регулярным графом ( А = 0, р = 2, ■и S (гть геометрия вершин и к т.к. графа Г < оотвегт твующт Г(о) для а € Г тбо S сильно s-однородна и одно in следцющиг утверждений верно

(1) t = а и Г есть граф являющийся ъвадратной решеткой на (s + 2)2 вершина i

(2) t = 2а, s < (2а- 1)(а f I)2, s + а П деатп 2ф + 1)(2а + 1). и Г сеть треуго ¡ьный граф на (s + 2)(2s 4- 3) вершина i

Пример 4. Сильно s-одпородная геомприя EGQ(s, 1) существует для в< е\ s = q — 2, гдр q ость с юпепь двойки [?|

Пучь тг = PG(2,q), а и Ь являются точками тг, L есть прямая аЬ, С гиперовал содержащий а и b лТ -шмруппа вс ex центральных коллипе-аций с центром а и осыо, содержащей Ь Тогда |Т| = q{q— 1), Т фиксирует все прямые, проходящие через а и является точно 2-тр<иинтншюИ группой на множестве прямых, проходящих чс^рез b и отличных or L

Множество точек юомефии EGQ(s, 1) соскип из точек 7Г которые не лежат на L, а множество блоков является объединением множества прямых 7Г, не содержащих а или Ь, и образов С — {Р, Q} под действием группы зданий Т

Пример 5 Сильно 3-одпородиая геометрия EpG2{"&,2) существует Пусть точечное множество S есть множество позиций г] квадратной ма i рицы порядка 5 а мпожеет во блоков В задано наборами {hi, 2i2, , 5ig}, такими, что перестановка (tit2 г5) имеет знак плюс

Ясно, что \В\ = 51/2 = (£+l)(s+l)(s + 2) дгш f = 2 s = 3 и f(a,B) = 3 для любого анзифлдга (а, В)

Далее для топки а = а:гх имеем |Ра| = 16, |£?а| = 16 каждая точка из Ра принадлежит трем блокам и? Ва п каждый блок из Ва г одержит 4 ючки in Ра Таким обра.зом (Р,В) являемся сильно З-одноро'щой геометрией EpG2{ 3,2)

Теорема 7. Пусть S является сильно (s — 1)-однородной геометрией EpGa(s,t) Тогда либо S является геоиетриеи EpG2X{3x,3x — 1) для некоторого нечетного х либо S = EGQ{3,1) EGQ{3,9) EpG2(6,15) EpG2(7,6) или EpG3{7,9)

Дж Тас построил частичную геометрию рСгДЗг.Зж — 1) с а* = 32п~2, с помощью сиреда гиперботичое кой квадрики ii проективном lipoc i ранет ве PG{An— 1,3) К нас тоищему времени извес ню существование такого сиреда то.1Ычо дтя случая п = 2

Ав юр выражае г глубокую признал ельность научному руководи гелю чл -корр PAII Махпеву A A за нос ишовку задач и постоянное внимание

ЛИТЕРАТУРА

1 Вюшлег А Е , Willbmik II A Block designs / Handbook of incidence geometry buildings and foundations cd F Buekenhout Elsevei Science, Amsterdam 1995, 349-383

2 Buekenhout F Foundations of incidence geometi у /' Handbook of incidence geometry buildings and foundations ed F Buekenhout Elsevcn Science, Amsterdam, 1995, G3-107

3 Buekenhout F, Pasnn P Finite diagiam geometries extending buildings / > Handbook of incidence geometiy buildings and ioundat ions ed F Buekenhout

Elsevei Science, Ainsteidaiu 1995 1143-1255

4 Tits J Buildings ol Splienc al Type and finite BN-pans Spimger Leetuie Notes m Mathematics, л 38G 19G8

5 Biouwei AE, Cohen AM, Neumaici A Distance-regular giaplis '/ Beilmetc Spimger-Verlag 1989

G Higman D G Finite peimutatiori gioups oi rank 3 ' Math Z 19G4 v 8G, 145-150

7 Higman D G Pnmitive lank 3 gioups with a prune subdegiee , / Math Z , 19GG, v 91 70-86

8 Higman DG Intel нес tiou inatncies loi finite permutation дюирь J Algebra, 1907, v G, 22-42

9 Hiftimm D G On finite afhne planes of rank 3 / ' Math Z , 19G8 v 104 117-149

10 Higrnan D G Characterization of families of lank 3 permutation gioups by the wibdegrees I II ' Arth Math , 1970, v 21, 151-156, 353-3G1

11 Piagei С E . Soulier L II Low tank lcpiesentations and graphs foi sporadic groups Lee tuie series 8 Cambridge Uiu\eisit/y press 1997

12 Воденев А А Кузнецов A II , Махпев А А Носов В В О хороших парах в реберно pei v пярпых i рафах / Дискрет магем 2003, т 15 77-97

13 Махиев А А О с ильиой регулярности некоюрых реберно регулярных Iраскоп , Извес тия РАН, сер матсм 2001, т 08,159-172

14 Ка зарина В II . Махпев А А О реберно рсчулярных графах с Ь\ = 5 // Ал1сбра, логика н киберпепжа Тем докл Иркутск 2004, 159-101.

15 Васильев С А , Махпев А А О вполне регулярных i рафах с bi = 4 / / И звес тпя Гометьс кото гос уи-та Гомель 200G, 101-108

16 Махпев А А , Мипакова И М Об автоморфизмах графов с Л = 1, ¡.1 = 2 ( Дискретная математика 2004, т 10 N1,95-104

17 Cameron Р Permutation Gioups, London Math Soc Student, Texts 45 Cambndge Urm Press - 1999

18 Cameron P, Fisher P H Small extended generalised quadiangles ч Europ Л Comb 1990, v 11 P 403-413

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

19 Мачнев А А, Нирова М С Слыго рсчуляриые трасты с Ь\ < 13 , Межд алгебр коне]) Тез докл Екатеринбург, изд-во Урал ун-та 2005 184-18G

20 Махпев А А , Нирова М С Узкие частичные четырехугольники и их ашоморфизмы ' ' Проблемы теор и приклад мат ем Труды 37-й Регион молод копф Изд-во ИММ УрО РА.Н, Екатеринбург 200G 58-G0

21 Махиев А А Нирова М С Узкие частичные четырехугольники и их авгоморфизмы / ' Алгебра и логика 200G, т 45, N б, 125 134

22 Махпен А А Кирова М С Об однородных расширениях час шчпых гоометьрий ''Проблемы'Iсор и приклад магом Труды 38-й Рсчпоп молод конф II !д-во ИММ УрО РАН Екатеринбург 2007. 40-49

23 Махнен А А Нирова М С Об однородных расширениях частичных геометьрш') /, Труды ИММ УрО РАН, Екаюринбург 2007. т 13

24 Нирова МС О вполне регулярных графах с Ь\ < 5 Сибирские чиектронные матома шчеекие извесшя 2007, т 4, 1-11

Подписано и иочачь 23 05 07 Формаг 00x84 1,, 1G Бума!л писчая

Плоская почать Тираж 100 жз Заказ

Ри 3oi рафия нлучно-ис< ледова гелм r<oi1 части ГОУ ВПО УГТУ-УПИ G20002, г Екатсрнпбурз ул Мира 19

Введение.

Глава 1. Регулярные графы с малыми значениями

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

§ 1.2. Почти хорошие тройки в реберно регулярных графах.

§ 1.3. Сильно регулярные графы с b\ < 18.

§ 1.4. Вполне регулярные графы с Ъ\ < 5.

Глава 2. Узкие частичные четырехугольники и их автоморфизмы.

§ 2.1. Параметры узких частичных четырехугольников.

§ 2.2. Автоморфизмы сильно регулярного графа с (400,21,2,1).

Глава 3. Однородные расширения частичных геометрий.

§ 3.1. О s-однородных расширениях геометрий pGa(s,t).

§ 3.2. Сильно (s—1)-однородные расширения геометрийpGa(s,t). Литература

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь — вершины графа Г, то через d(a, Ь) обозначим расстояние между а и 6, а через Г; (а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии г от вершины а. Подграф Гх (а) будем называть окрестностью вершины а и обозначать через [а]. Через а1 обозначим подграф, индуцированный {a} U [а].

Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Число вершин в [а] П [b] обозначим через Л(а, 6) (/i(a, &)), если d(a,b) = 1 (d(a,b) = 2), а соответствующий подграф назовем (//-) А-подграфом. Граф Г назовем реберно регулярным с параметрами (v,k: Л), если он содержит v вершин, регулярен степени к, и каждое его ребро ab лежит в Л треугольниках. Граф Г — вполне регулярный граф с параметрами (г;, к, А, /г), если он реберно регулярен с соответствующими параметрами и [а] П [Ь] содержит \i вершин для любых двух вершин а, Ъ, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.

Через -K"mi,.,m„ обозначим полный n-дольный граф, с долями порядков mi, ., тп. Если mi = . = тп = ш, то соответствующий граф обозначается через Кпхт. Треугольным графом Т(т) называется граф с множеством неупорядоченных пар из X в качестве вершин, \Х\ = т и пары {a,b},{c,d} смежны тогда и только тогда, когда они имеют общий элемент. Граф на множестве вершин X х Y называется т х п решеткой, если |Х| = т, \Y\ = п и вершины (xi,yi), (£2,2/2) смежны тогда и только тогда, когда х\ = Х2 или yi = у2.

Графом Джонсона J(n,m) называется граф, вершинами которого являются m-элементные подмножества данного n-элементного множества, причем две вершины а, b смежны, только если \а П b\ = т — 1. Граф Пэ-ли P(q) в качестве вершин имеет элементы поля Fq, q = 1 (mod 4), и две вершины а, Ь смежны, только если Ъ — а является ненулевым квадратом в Fq. Граф Петерсена — это дополнительный граф для треугольного графа Т{5) (он имеет параметры (10,3,0,1)). Граф Клебша (Шлефли) — это единственный сильно регулярный граф с параметрами (16,10,6,6) (с параметрами (27,16,10,8)). Граф Шрикханде — это единственный сильно регулярный локально шестиугольный граф с параметрами (16,6,2,2). Имеется точно 3 сильно регулярных графа, имеющих параметры графа Т(8), но не изоморфных Т(8). Эти графы называются графами Чанга. Графом Хофмана-Синглтона называется единственный сильно регулярный граф с параметрами (50,7,0,1). Графом Хигмена-Симса называется единственный сильно регулярный граф с параметрами (100,22,0,6).

Частичной геометрией pGa(s,t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Если а = t, то геометрия называется сетью. Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Легко понять, что точечный граф частичной геометрии pGa(s,t) сильно регулярен с параметрами v = (s+l)(l-t-st/a), k = s(t+l), A = (s — 1) + (a — 1 )t, fi = a(t +1). Любой сильно регулярный граф с такими параметрами для некоторых a, s, t называется псевдогеометрическим графом для pGa(s,t).

Множество вершин графа MZ(n), отвечающего аффинной плоскости 7г = (X, С) порядка п, совпадает с X U С, причем подграф X является кокликой, точка смежна с прямой, только если она принадлежит этой прямой и две прямые смежны, если они не пересекаются. Граф MZ(n) имеет п(2п + 1) вершин, является кореберно регулярным с ц = 1, причем Х(а,Ь) = 0, если одна из этих вершин — точка, а другая — содержащая эту точку прямая, A (a, b) = п — 2, если а и Ъ — параллельные прямые.

Частичным четырехугольником PQ(s,t:/j,) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любых двух несмежных точек пересечение их окрестностей в точечном графе является //-кокликой. Точечный граф частичного четырехугольника PQ(s, t, ц) сильно регулярен с параметрами v = 1 + s(t + 1) + s2t{t + 1)//х, k = s(t + 1) и A = s — 1. Частичный четырехугольник назовем узким, если t < 6.

Граф Г диаметра d называется дистанционно транзитивным, если для любого i G {0,.,d} и для любых вершин u,v,x,y с условиями d(u,v) = d(x, у) = г, существует автоморфизм g графа Г такой, что (и9, vg) = (х, у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Более половины спорадических групп имеют представления в виде групп автоморфизмов графов ранга 3 [39].

Если вершины и, w находятся на расстоянии i в Г, то через Ьг-(и, w) (через C{(u,w)) обозначим число вершин в пересечении ri+i(u) (в пересечении Гг1(и)) с [и;]. Дистанционно регулярным графом называется граф диаметра d, в котором для любого г 6 {0,1,d} параметры b{(u, w) и Ci(u, w) не зависят от выбора вершин и, w, а зависят только от расстояния между этими вершинами в графе Г.

Заметим, что в реберно регулярном графе с параметрами (v, к, А) значение b\(u, w) не зависит от выбора ребра {и, w} и равно к — А — 1.

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

Пусть G — транзитивная группа подстановок на множестве Q. Если подгруппа Gp группы G, состоящая из всех подстановок, фиксирующих точку а 6 П, имеет г орбит, то говорят, что G является группой ранга г. Пусть г = 3 и соответствующие 3 орбиты — это {а}, Г(а), А(а). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого - Пи две вершины р, q смежны в Г, если р G T(q) [30].

Д.Хигмен [30-34] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, т. е. дистанционно транзитивных графов диаметра 2.

Ярким примером перехода от изучения групповых симметрий к комбинаторным является расширение класса дистанционно транзитивных графов до класса дистанционно регулярных графов. В настоящее время при исследовании графов и конечных геометрий вовлекаются симметрии все более общего вида.

Поскольку каждый дистанционно регулярный граф является вполне регулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов.

В диссертации получено описание вполне регулярных графов с Ь\ < 5 и найдены параметры сильно регулярных графов с Ь\ < 18; изучены узкие частичные четырехугольники и доказано, что сильно регулярный граф с параметрами (400,21,2,1) не является вершинно транзитивным; классифицированы s-однородные и сильно (s — 1)-однородные расширения частичных геометрий pGa(s, t).

Результаты работы докладывались на Международной алгебраической конференции, посвященной 70-летию JT.H. Шеврина (Екатеринбург, 2005), на Международных конференциях "Мальцевские чтения" (Новосибирск, 2005 и 2006), на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения А.И. Старостина (Приэльбрусье, 2006), на 37-й и 38-й Региональных молодежных конференциях ИММ УрО РАН, на алгебраических семинарах Института математики и механики УрО РАН.

Основные результаты опубликованы в работах [13-19]. Работы [13-18] были написаны в нераздельном соавторстве с Махневым А.А.

Диссертация состоит из введения, трех глав и списка литературы (43 наименования). Ссылка на теорему i.j означает, что она находится под номером j в главе i. Ссылка на утверждение i.j.к означает, что оно находится под номером к в параграфе j главы i.

1. Белоусов И.Н., Гурский Е.И., Дергач А.С., Махнев АА. О почти хороших парах в реберно регулярных графах // Проблемы теор. и приклад, матем. Труды молодежной конфер. Екатеринбург 2004, 9-11.

2. Белоусов И.Н., Махнев А А. О почти хороших парах вершин в реберно регулярных графах // Известия Урал. гос. ун-та, Екатеринбург 2005, N 7, 35-48.

3. Васильев С.А., Махнев А.А. О вполне регулярных графах с Ъ\ = 4 // Известия Гомельского гос. ун-та, Гомель 2006, 101-108.

4. Веденев А.А., Кузнецов А.Н., Махнев А.А., Носов В.В. О хороших парах в реберно регулярных графах // Дискрет, матем. 2003, т. 15, 77-97.

5. Зарипов С.Р., Махнев А.А., Яблонко И.П. Реберно регулярные графы диаметра 2сА > 2&/3 — 2 // Труды Украинского матем. конгресса, Киев 2001, секция 1: Алгебра и теория чисел, Институт математики НАН Украины, Киев 2003, 46-61.

6. Кабанов В.В., Махнев А.А. Об отделимых графах с некоторыми условиями регулярности // Матем. сборник 1996, т. 187, N 9, 495-503.

7. Казарина В.И., Махнев А.А. О реберно регулярных графах с Ь\ = 5 // Алгебра, логика и кибернетика. Тез. докл. Иркутск 2004, 159-161.

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

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

10. Махнев А.А. О сильной регулярности некоторых реберно регулярных графов // Известия РАН, сер. матем. 2004, т. 68, 159-172.

11. Махнев А.А., Минакова И.М. Об одном классе реберно регулярных графов // Известия Гомельского ун-та 2000, 145-154.

12. Махнев А.А., Минакова И.М. Об автоморфизмах графов с А = 1, /х = 2 // Дискретная математика 2004, т. 16, N 1, 95-104.

13. Махнев А.А., Нирова М.С. Сильно регулярные графы с &i < 13 // Межд. алгебр, конф. Тез.докл. Екатеринбург, изд-во Урал, ун-та 2005, 184-186.

14. Махнев А.А., Нирова М.С. Узкие частичные четырехугольники и их автоморфизмы // Проблемы теор. и приклад, матем. Труды 37-й Регион, молод, конф. Изд-во ИММ УрО РАН, Екатеринбург 2006, 58-60.

15. Махнев А.А., Нирова М.С. Узкие частичные четырехугольники и их автоморфизмы // Алгебра и логика 2006, т. 45, N 6, 125-134.

16. Махнев А.А., Нирова М.С. Об однородных расширениях частичных геометрий // Проблемы теор. и приклад, матем. Труды 38-й Регион, молод, конф. Изд-во ИММ УрО РАН, Екатеринбург 2007, 46-49.

17. Махнев А.А., Нирова М.С. Сильно регулярные графы с Ь\ < 18 // Известия вузов, математика 2007.

18. Махнев А.А., Нирова М.С. Об однородных расширениях частичных геометрий // Труды ИММ УрО РАН, Екатеринбург 2007, т. 13.

19. Нирова М.С. О вполне регулярных графах с Ь\ < 5 // Сибирские электронные математические известия 2007, т. 4, 1-11.

20. Bous R.C., Dowling Т.A. A generalization of Moore graphs of diameter 2 // J. Comb. Theory (B) 1971, v. 11, 213-226.

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

22. Brouwer A. E., van Lint J. H. Strongly regular graphs and partial geometries // Enumeration к Designs / D. Jackson and S. Vanstone, eds.,Academic Press 1984, 85-122.

23. Brouwer A. E., Willbrink H. A. Block designs // Handbook of incidence geometry: buildings and foundations, ed. F. Buekenhout. Elsever Science, Amsterdam, 1995, 349-383.

24. Buekenhout F. Foundations of incidence geometry // Handbook of incidence geometry: buildings and foundations, ed. F. Buekenhout. Elsever Science, Amsterdam, 1995, 63-107.

25. Buekenhout F, Pasini P. Finite diagram geometries extending buildingsHandbook of incidence geometry: buildings and foundations, ed. F. Buekenhout. Elsever Science, Amsterdam, 1995, 1143-1255.

26. Cameron P. Partial quadrangles // Quart. J. Math. Oxford (2) 1975, v. 26, 61-73.

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

28. Cameron P., Fisher P. H. Small extended generalized quadrangles // Europ. J. Comb. 1990, v. 11, 403-413.

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

30. Higman D.G. Finite permutation groups of rank 3 // Math. Z. 1964, v. 86, 145-156.

31. Higman D.G. Primitive rank 3 groups with a prime subdegree // Math. Z. 1966, v. 91, 70-86.

32. Higman D.G. Intersection matricies for finite permutation groups // J. Algebra, 1967, v. 6, 22-42.

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

34. Higman D.G. Characterization of families of rank 3 permutation groupsby the subdegrees I, II // Arth. Math. 1970, v. 21, 151-156; 353-361.

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

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

37. Hughes D.R. Extended partial geometries: dual 2-designs, Europ. J. Comb. 1990, v. 11, 459-472.

38. Payne S., Thas J. Finite Generalized Quadrangles. Research Notes in Math. 1984, v. 110. Pitman: Boston.

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

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

41. Thas J.A. Some results on quadrics and new partial geometries // Simon Stevin 1981, v. 55, 129-139.

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

43. Wilbrink H.A., Brouwer A.E. (57,14,1) strongly regular graph does not exist // Proc. Kon. Nederl. Akad. Ser. A 1983, v. 45, 117-121.