Графы Кэли групп Zd и пределы конечных вершинно-примитивных графов тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Костоусов, Кирилл Викторович

• Костоусов, Кирилл Викторович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Костоусов, Кирилл Викторович

Введение. Формулировки основных результатов

1 Графы Кэли групп Ъй и конечные группы целочисленных матриц

1.1 Критерий изоморфности графов Кэли групп I/1: доказательство теоремы 1.

1.2 Связь графов Кэли групп Ъй с конечными группами целочисленных матриц: доказательство теоремы 2. И

1.3 О пределах вершинно-примитивных графов НА-типа.

2 Реберно-транзитивные графы Кэли групп И1 и пределы графов, допускающих реберно-транзитивную вершинно-примитивную группу автоморфизмов ЯА-типа

2.1 Реберно-транзитивные графы Кэли группы Ъ и Ит(ТТ>е1^ап8): доказательство теоремы 3.

2.2 Реберно-транзитивные графы Кэли групп с? > 2, и Ит^Р^0™): доказательство теоремы 4.

3 Минимальные графы Кэли групп Ъл и пределы графов минимальной валентности для вершинно-примитивных групп НА-типа

3.1 Графы Кэли групп наименьшей валентности как пределы минимальных вершинно-примитивных графов ЯА-типа.

3.2 Минимальные графы Кэли группы Ъ2 и доказательство теоремы 5.

3.3 Минимальные графы Кэли группы 1} и Хш^ТТ1^1])'- доказательство теоремы 6.

3.4 Графы Кэли группы Zd, соответствующие орбитам конечной группы целочисленных матриц.

3.5 Алгоритмы, позволяющие находить минимальные графы Кэли групп 7/1, соответствующие орбитам фиксированной конечной группы целочисленных матриц.

3.6 Схема нахождения минимальных графов Кэли группы Zd при d >

4 Минимальные графы Кэли группы Z4 и пределы графов минимальной валентности для вершинно-примитивных групп НА-типа

4.1 Подгруппы бесконечного орбитного типа в GL^Z): доказательство теоремы 7.

4.2 Минимальные графы Кэли группы Z4 и доказательство теоремы 8.

Введение диссертации (часть автореферата) на тему «Графы Кэли групп Zd и пределы конечных вершинно-примитивных графов»

Всюду ниже под графом понимается неориентированный граф без петель и кратных ребер. Множество вершин графа Г обозначается через У(Г), а множество ребер — через Е(Т). Под автоморфизмами графа Г понимаются подстановки на множестве К(Г), сохраняющие отношение смежности.

Граф называется вершинно-примитивным, если он допускает группу автоморфизмов, действующую примитивно на множестве его вершин. Класс конечных связных вершинно-примитивных графов будем обозначать через ТТ (здесь и всюду ниже под классом некоторых графов понимается множество изоморфных типов этих графов). Важный в комбинаторике и алгебре подкласс класса ТТ составляют графы, допускающие вершинно-примитивную реберно-транзитивную группу автоморфизмов. Этот класс обозначается через ЯРе-'Г£Ш5. Класс в свою очередь, имеет важный подкласс ТТ™п, состоящий из графов минимальной валентности для конечных вершинно-примитивных групп. Связный граф Г называется графом минимальной валентности для вершинно-примитивной группы автоморфизмов С?, если Г имеет наименьшую валентность среди всех связных графов А, таких что У(А) = У (Г) и (3 < Аи^Д). Каждая примитивная группа подстановок может быть реализована как группа автоморфизмов некоторого связного вершинно-примитивного графа. При этом вершинно-примитивные графы минимальной валентности для заданной примитивной группы доставляют наиболее естественные ее реализации в качестве группы автоморфизмов графа.

Для изучения класса ТТ в [5] и [8] был предложен подход, связанный с изучением предельных графов для класса ТТ. Если С — произвольный класс конечных связных вершинно-примитивных графов, то предельными для С называются бесконечные связные графы, у которых каждый шар изоморфен шару некоторого графа из С. Класс предельных для С графов обозначается через Нш(С). Описание Нш(С) доставляет описание типичного локального строения графов из С. Вопрос о строении графов из Хиа^ТТ) был поставлен В.И. Трофимовым в [2, вопрос 12.89]. В силу сказанного выше, также представляет интерес изучение строения графов из Х\т{ТТ>е~1гап8) и Нт(^Г7>тгп). Заметим, что, как показано в [8], строение графов из Х\т{РРе~1гап8) во многом определяет строение произвольных графов из \\т{ТР).

В [8] М. Гиудичи, Ч. Ли, Ч. Прэгер, А. Серешем и В.И. Трофимовым было начато систематическое изучение класса \[т(ТР). При этом была показана важность подклассов ТРна, РРаб, Р'Рра класса ТР, определяемых следующим образом. Пусть (7 — примитивная группа подстановок на конечном множестве V и V £ V. Группа С? называется примитивной группой НА-типа, если она содержит регулярную абелеву нормальную подгруппу. Группа (7 называется примитивной группой АБ-типа, если она почти проста, т.е. 1пп(Т) < б? < АиЬ(Т) для некоторой конечной неабелевой простой группы Т. Наконец, группа (7 называется примитивной группой РА-типа, если С имеет единственную минимальную нормальную подгруппу N = Тк, где Т — некоторая конечная неабелева простая группа, к > 2, и стабилизатор элемента г; в ./V проектируется на (нетривиальные) собственные подгруппы прямых простых факторов группы N. Для X 6 {НА, Ав, РА} через ТРх обозначается класс графов, допускающих вершинно-примитивную группу Х-типа, через ргре-и-апв обозначается подкласс класса ТРх, состоящий из графов, допускающих реберно-транзитивную вершинно-примитивную группу Х-типа, а через гртгп обознается подкласс класса ^гре-1гапз} состоящий из графов минимальной валентности для вершинно-примитивных групп Х-типа.

Из [8, теор. 1] следует, что

Х\т(ТР) = Х\т(ТРНА) и Нт(ЯРЛ5) и Пш{ТРРА), хш{ТТе-1гапз) = Ит{ТРенТП8) и Ит{ТРе^гапз) и Нт(ТРе^гапз),

Ит{ТР™п) = Нти Нт(ТР%п) и Нт(ТР^).

Поэтому представляющее самостоятельный интерес изучение классов Нт{ТРна), Нт{РРе^апз) и Нт{ТР^а) является вместе с тем необходимым этапом изучения классов Нт(ТР), \\т(ТРе~1гап$) и Нт(ТРтЫ).

Пусть В — конечнопорожденпая абелева группа и М — конечная система порождающих группы В такая, что М = —М и 0 £ М. Графом Кэли группы В, соответствующим системе порождающих М, называется граф Тв,м с множеством вершин У(Гв,м) = В и множеством ребер Е(Тв,м) = {{а>^} : а-ЬеМ}.

Пусть й — положительное целое и Аи^Г^д^о — стабилизатор вершины 0 в группе автоморфизмов графа Кэли группы Ъй, соответствующего системе порождающих М. Граф Г^м назовем минимальным графом Кэли группы I/1, если множество М является Аи^Г^д^о-орбитой наименьшей мощности на Zíг\ {0}. Класс всех графов Кэли группы обозначим через Сау^), подкласс всех реберно-транзитивных графов класса Сау(2^) обозначим через Сауе~*гаТ15(2^), а подкласс всех минимальных графов Кэли группы Ъл класса Сауе~*гапв(2!1) обозначим через Сау™п(^).

По [8, теор. 2] каждый граф из Нт{ТТна) лежит в Сау^) для некоторого (1. При этом, поскольку каждый предельный граф для класса реберно-транзитивных графов является реберно-транзитивным (см. [8]), то каждый граф из 1\т(ТТе£дап8) лежит в С&уе~*гапа(%*) для некоторого А. Кроме того, из [8, теор. 2] и определения предельного графа следует, что каждый граф из лежит в Саутт(2^) для некоторого д. В связи с этим актуальными являются следующие две задачи, рассмотрению которых посвящена настоящая диссертация.

1) Исследовать Сауе-<гопв(йй) ПНт(^Ре£^гапз) для фиксированных значений д.

2) Исследовать Саутт(2^) П Нт(ТТ™/) для фиксированных значений <1.

Заметим, что описание графов из С&уе~1тт8 (Ъл) Г) Нт(ЯР^гапз) (соответственно из Саутш^) ПНт^Рял) ) Для всех ^ не превосходящих некоторого положительного целого числа п, доставляет, в частности, описание класса всех графов валентности, не превосходящей 2п + 2, лежащих в Нт(3:Т>е£дап8) (соответственно в Нт^^ял))■ Иллюстрацией этого замечания служит следствие 1 (см. ниже).

Реализуемый в диссертации подход к исследованию задачам 1) и 2) опирается на теоремы 1 и 2 из главы 1.

Теорема 1 доставляет эффективный метод проверки изоморфности графов Кэли групп Прежде, чем ее сформулировать, естественным образом отождествим группу Ъл с множеством целочисленных вектор-строк длины й с операцией покоординатного сложения и через СЬ^(й) обозначим группу целочисленных й х ¿-матриц с определителями ±1.

Теорема 1. Пусть Мг- — конечная система порождающих группы такая что 0 0 М{ и = -Мг, для ¿ = 1,2. Тогда a) Графы Кэли и Гй<г2,м2 изоморфны тогда и только тогда, когда ¿2 и М2 = М\а для некоторой матрицы а £ СЬ^ (Ж). b) Каждый изоморфизм графа Г^ М1 на граф м2 задается формулой х 1-+ ха + у, х 6 , для подходящих а € СЬ^(Й), у £ Zdl.

В теореме 2 устанавливается связь реберно-транзитивных и минимальных графов Кэли группы Ъ3, с конечными подгруппами группы СЬ^(Й). Перед ее формулировкой введем следующие определения.

Пусть <0^ — ¿-мерное векторное пространство над полем (О?, элементами которого являются рациональные вектор-строки длины Для г 6 {1,., й] через еф- обозначим вектор-строку длины с?, у которой на г-м месте стоит 1, а на остальных — 0. Всюду далее вместо е^ будем писать е^, опуская первый индекс (он всегда может быть восстановлен из контекста). Для М С <0? через (М)+ будем обозначать подгруппу аддитивной группы векторов пространства О1, порожденную множеством М, а через (М)о, будем обозначать подпространство векторного пространства на О6', натянутое на М. Через СЬ^А])) обозначим группу невырожденных й х «¿-матриц над <0>, а через Е^ — единичную с1х(1 матрицу.

Для конечной подгруппы й группы вЬ^Й) определим число т(в) := : а; £ \ {0}}, множества

Мъ(в) := {хв : ж € Ъй \ {0}, \хв\ = т(в),хО = -хв, {хС)+ = Ъй},

Мъ{С) := {хв : ж е О* \ {0}, \хв\ = т(С), = -хв, dim({жG>Q) = и классы графов

0де~1гапз(0) := {Т{х0)+,хС : * е 0й \ {0},хО= -хО, ¿\т((хС)®) = с*}, 0дт1п(0) := {Г(М)+)М : М €

Теорема 2. Пусть Сп,.,^ — все с точностью до сопряжения в С1^((0>) конечные подгруппы группы (^¿{Щ, содержащие —Е^. Тогда класс Сауе~*гап8(йсг) (соответственно класс Саутт(^) ) совпадает с классом иг€{1,.,п} Оде-*гапз(С{) (соответственно с классом Ц6{1,.,п} О0™п(О{) ).

В силу теоремы 2 для явного описания классов Сау6'1™™ (I/1) и Саутт(й<г) требуется выбрать представителей различных изоморфных типов графов из Цб{1,.,п}Ове~1гаП$(СЛ и Це{1 соответственно. Для этого используется, в частности, теорема 1.

Глава 2 диссертации посвящена изучению классов Сау6-*74""(ЪЛ) П

И т(ТТенАаПЗ) ПРИ ^ > 1.

Описание класса Сауе~*гатгг!(й) Г) Нт^Т^™"*) (а, вместе с тем, и класса Сау™п(й) П Нш(ТТн1а) ) Дает следующая теорема.

Теорема 3. Классы Съуе~1гапз{Ъ) П \\т{РГе£%апз) и Саутг'п(^ П Ит(ЯР^) совпадают и содержат единственный граф Г^!,-!}.

При й > 2 получен следующий результат о строении класса С&уе~1гапв {7$) П

Мт(ТТенАапВ)

Теорема 4. Класс Сще~1гаП8(Ъ6-) П Ит(РТенАаП8) бесконечен для каждого д>2.

При доказательстве теоремы 4 для каждого d > 2 явным образом строится счетное множество попарно не изоморфных графов Кэли группы Zd, лежащих в lim

Главы 3-6 диссертации посвящены изучению классов Caymm(Zd) П \im(J7'P1jjA) ПРИ d>2 на основе теорем 1 и 2.

В главе 3 получены следующие описания классов Caymm(Z2) П Нш^'РяХ) и Cay™'n(Z3)nlim(^?S).

Теорема 5. Cay™n(Z2) = {Гадд, Гад,Л С М2Д = еь е2}, М2)2 = ±{ei, е2, е\ + е2}.

Теорема 6. Caymi"(Z3) = С Um(^PSj), где Мзд - ±{ei,e2,e3}.

Использование теорем 1 и 2 для описания класса Caymw(Zd) П при d > 4 требует больших вычислений. В связи с этим в главе 3 описана схема нахождения минимальных графов Кэли группы Zd с использованием системы GAP [12].

Как видно из теорем 3, 5 и 6, класс Caymm(Zd) П lim{TV^D конечен при d < 3. Однако, как вытекает из следующей теоремы 7, доказываемой в главе 4, для d = 4 это уже не так. Для ее формулировки нам понадобится следующее определение, естественно возникающее в связи с теоремой 2.

Будем говорить, что конечная группа G Е GL^(Z) имеет бесконечный орбит-ный тип, если класс OQmm{G) бесконечен. В противном случае будем говорить, что группа G имеет конечный орбитный тип. Из определения легко следует, что свойство конечной группы из GL^(Z) иметь бесконечный орбитный тип инвариантно при сопряжении в GL^(Q).

Теорема 7. С точностью до сопряжения в GL^Q) подгруппы бесконечного орбитпого типа группы GL^Z) исчерпываются группами Gi = (/ii,/^), G2 = (/ь/2,/з>,£з = (<?2,/4>, где

0 0 -1 -п /0 -1 -1 -1)

0 -1 -1 -1 h2 = 0 -1 0 -1

0 0 0 -1 1 -1 -1 0

-1 1 1 1 У \о 1 0 0 )

-1 1 1 0 \ / 0 -1 0 -1\

-1 0 0 -1 /2 = 1 -1 -1 -1

-1 1 1 1 -1 0 0 -1

1 0 -1 0 J V 0 1 1 1 /

-1 0 1 0 \ ( 0 0 0 \

0 0 1 1 , /4 = -1 1 0 0

-1 0 0 0 -1 0 1 0

1 -1 -1 -1 / V 1 -1 -1 -1 /

С?1 ^ йз X 28, G2^¿Q8X Ъъ, Сз = X 22).

Описание класса Саутт(24) П Ит(ТТнг2) Дает следующая теорема, доказательство которой приводится в главе 4.

Теорема 8. Минимальные графы Кэли группы Ъ4- с точностью до изоморфизма исчерпываются графами Кэли группы 1}, соответствующими следующим системам порождающих: М4Д = ±{е1,е2,е3,е4}, М4)2 = ±{еь е3, е4, е\ + е2, е2 + е3 + е4}, М4)3 = ±{е1, е2, ез, е4, ех - е2, е3 - е4}, элементам из 1) (все они порядка 24).

Бее минимальные графы Кэли группы лежат в Ит(ТТн12).

В главах 5 и 6 получены, соответственно, следующие описания классов Саутг'"(25) П и Саутг'"(26) П

Теорема 9. Саутг>г(25) - {Г^д, Г^Л С где

М5)2 = Мх и ±{б! + е2 + е3 - е4 - е5}.

Теорема 10. Сау™п{Ъ6) = : % е {1,., 7}} С где

М6Д = ±{ег-:ге{1,.,6}},

М6,2 = ±{еь е2, ез, е6, ех - е4, е2 - е5, е3 - е4 + е5 - е6}, М6Д и ±{ех - е2, е3 - е4, е5 - еб}, Мед = М6д и ±{ех - е2 + е4, ех - е3 + е5, е2 - е3 + е6, е4 - е5 + еб}, Мз,5 = (б1 - 63)^1 порядка 36, -ОДз.б = порядка 42, Мб,7 = порядка 54; где

1 0 1 1 1 -1\ ( 0 0 0 -1 0 -1 \

1 0 0 1 1 0 0 1 1 0 0 -1

0 1 1 0 0 -1 -1 0 0 0 0 0

-1 0 0 0 -1 1 7 1 -1 -1 0 0 0

0 0 0 0 1 0 -1 1 0 0 -1 1

V 1 0 1 0 1 -1/ V-! 1 0 0 0 0 /

О 1

1 о о о

О 1 о о \1 о о 0

1 -1 о -1 о о о о о о о о 0

1 о о о о -1 о о

О 1 о о

0 о

1 о о о

1 о о о

0 о

1 1 -1 -1 О -1 -1 -1 о о о о о -1 о\ 1 о 0

1 1/

0 0 1 0 0 0 \ /1 -1 -1 -1 0 0\

1 0 1 0 1 -1 0 0 -1 -1 -1 0

-1 1 1 1 0 0 0 -1 0 -1 0 0

0 0 - -1 0 -1 1 > 0 0 0 1 1 0

0 0 0 0 1 0 0 0 0 0 -1 0

V -1 1 1 0 0 0 \0 -1 -1 -1 -1 1/

0 1 1 1 1 0 \

0 0 1 1 1 0

0 0 -1 0 0 1 \

0 0 0 1 -1 0

1 -1 0 0 1 -1

1 0 0 1 1 0

Полученные результаты о строении класса Саутш(Ж^)ПНт(^Р^) при ¿<6 дают следующее описание графов малой валентности из

Следствие 1. Следующий список содержит все графы из Ххт^ТТ^д), валентность которых не превосходит 14;

1) Г2,{ 1,-1} валентности 2,

2) Г22,±{еье2} валентности 4,

3) Гга,±{в1)е2,е1+е2} валентности 6,

4) ^ъ\±{еие2,ег} валентности 6,

5) Г%*,±{е1,е2,е3,е*} валентности 8,

6) Г24)±{еье3;е4)е1+е2)е2+ез+е4} валентности 10,

7) гж^±{е1,е2,е31е4,е4} валентности 10,

8) Гг«>±{е1,е2,ез,е41е1-е!1)ез-е4} валентности 12,

9) Гг» ,±{еье2,ез,е4,е5,е1+е2+ез-е4-е5} валентности 12, ю) г2. ,±{б1 ,е2,ез,е4,е5,е6} валентности 12,

11) Гр ,±{е1,е2,ез,е6,е1-е4,е2-е5,ез-е4+е5-е6} валентности 14,

12) Г2т ,±{е1,е2,ез,е4,е8>ев,е7} валентности 14.

Список литературы диссертационного исследования кандидат физико-математических наук Костоусов, Кирилл Викторович, 2007 год

1. Жидков, Н.П. Геометрия кристаллического пространства / Н.П. Жидков, Б.М. Щедрин // М.: изд-во Моск. Ун-та, 1988.

2. Коуровская тетрадь. Нерешенные вопросы теории групп. Новосибирск: Но-восиб. гос. ун-т., 2002.

3. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део // М.: Мир, 1980.

4. Трофимов, В.И. Ограниченные автоморфизмы графов и одна характери-зация решеток / В.И. Трофимов // Изв. АН СССР. Сер. матем. 1983. Т. 47. т. С. 407-420.

5. Трофимов, В.И. О действии примитивных групп / В.И. Трофимов // Алг. и лог. 1989. Т. 28. №3. С. 337-369.

6. Bass, Н. The degree of polynomial growth of finitely generated nilpotent groups / H. Bass // Proc. London Math. Soc. 1972. V. 25. P. 603-614.

7. Brown, H. Crystallographic Groups of Four-Dimensional Space / H. Brown, H. Bulow, J. Neubuser, H. Wondratschek, H. Zassenhaus // New York: John Wiley, 1978.

8. Giudici, M. On limit graphs of finite vertex-primitive graphs / M. Giudici, C.H. Li, C.E. Praeger, A. Seress, V. Trofimov //J. Comb. Theory. Ser. A. 2007. V. 114. P. 110-134.

9. Opgenorth, J. Crystallographic Algorithms and Tables. / J. Opgenorth, W. Plesken, T. Schultz // Acta Cryst A. 1998. V. 54. P. 517-531.

10. Plesken, W. Counting crystallographic groups in low dimensions / W. Plesken, T. Schulz // Experimental Mathematics. 2000. V. 9. P. 407-411.

11. CARAT — Crystallographic AlgoRithms And Tables. Version 2.0 (http://wwwb.math.rwth-aachen.de/carat/).

12. The GAP Group. GAP — Groups, Algorithms, and Programming, Version 4.4, Aachen, St Andrews, 2004 (http://www.gap-system.org).

13. Maple — comprehensive computer system for advanced mathematics, Version 8 (http://www.maplesoft.com).Работы автора по теме диссертации

14. Костоусов, К.В. Графы Кэли группы Zd и пределы вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Проблемы теоретической и прикладной математики. Труды 36-й региональной молодежной конференции. Екатеринбург, УрО РАН. 2005. С. 44-46.

15. Костоусов, К.В. Графы Кэли группы Zd и пределы минимальных вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Проблемы теоретической и прикладной математики. Труды 37-й региональной молодежной конференции. Екатеринбург, УрО РАН. 2006. С. 50-52.

16. Костоусов, К.В. Графы Кэли группы Z4 и пределы минимальных вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Проблемы теоретической и прикладной математики. Труды 38-й региональной молодежной конференции. Екатеринбург, УрО РАН. 2007. С. 40-43.

17. Костоусов, К.В. Графы Кэли группы 7Ld и пределы вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Сиб. мат. журнал. 2007. Т. 48. №3. С. 606-620.

18. Костоусов, К.В. Графы Кэли группы Z4 и пределы минимальных вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Алгебра и логика (в печати).

19. Костоусов, К.В. О графах Кэли группы Z4, являющихся предельными для множества минимальных вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Труды ИММ УрО РАН. 2007. Т. 13. №1. С. 132-147.

20. Костоусов, К.В. Графы Кэли групп Z5 и Z6 и пределы вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Международная конференция "Алгебра и ее приложения": Тезисы докладов. Красноярск. 2007. С. 77-79.