Графы Кэли групп 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&trade-&trade- (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,/з>,?з = ( , где.

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 -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.

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.