Симметрические расширения графов

Диссертационная работа посвящена изучению симметрических расширений графов. Пусть Г и, А — графы (под графом здесь и далее понимается неориентированный граф без петель и без кратных ребер). В соответствии с [1] связный граф Г называется симметрическим расширением графа Г посредством графа А, если существуют такая вершинно-транзитивная группа С автоморфизмов графа Г и такая система импримитивности, а группы С на множестве У (Г) вершин графа Г, что фактор-граф Г/сг изоморфен графу Г и блоки системы и порождают в Г подграфы, изоморфные графу А. Ясно, что симметрическое расширение графа Г посредством графа, А существует лишь для Г и А, допускающих вершинно-транзитивные группы автоморфизмов, причем граф Г должен быть связным. Если в приведенном выше определении симметрического расширения графа Г посредством графа, А отказаться от условия связности графа Г, то получим определение обобщенного симметрического расширения графа Г посредством графа А. Если при этом (р — изоморфизм графа Г ¡-а на граф Г, то будем говорить, что Г — обобщенное симметрическое расширение графа Г посредством графа А, реализуемое С, а, р.

Симметрические расширения графов представляют интерес в силу целого ряда причин (см. ниже). При этом часто бывает важно, чтобы (в приводимом выше определении симметрического расширения Г посредством А) при изоморфизме Г/сг на Г индуцируемая С группа С7 автоморфизмов графа Г/сг переходила в некоторую заданную группу автоморфизмов 6? графа Г. В связи с этим вводится следующее определение (см. [1]). Для графов Г, А и вершинно-транзитивной группы автоморфизмов С графа Г связный граф Г называется С-симметрическим расширением графа Г посредством графа А, если граф Г является симметрическим расширением графа Г посредством графа А, реализуемым такими С, сг, что (рС7(р~1 = С. Если в этом определении отказаться от условия связности графа Г, то получим определение обобщенного С-симметрического расширения графа Г посредством графа, А (реализуемого С, сг, <р).

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

1) Понятие симметрического расширения одного графа посредством другого графа аналогично хорошо известному понятию расширения одной группы посредством другой группы. Связь между расширениями групп и симметрическими расширениями графов можно формализовать следующим образом. Пусть С — группа с системой порождающих М такой, что 1 ф М = М-1, N — нормальная подгруппа группы С, С = С/Я и М = {дИ: д (Е М Щ. Тогда граф Кэли Г^^ группы С, построенный по системе порождающих М, является С-симметрическим расширением графа Кэли Гв, м группы С, построенного по системе порождающих М, на котором С действует естественным образом, посредством графа Кэли группы Л^, построенного по множеству М П N. В связи с этим изучение симметрических расширений графов представляет интерес для теории групп.

2) Ряд известных конструкций теории графов, если их применить к вер-шинно-симметрическим (т.е. допускающим транзитивные на вершинах группы автоморфизмов) графам Г и А, приводят к симметрическим расширениям Г посредством А. Такими конструкциями являются, например, декартово, прямое, лексикографическое и некоторые другие произведения (см. [2]). К симметрическим расширениям графов приводит также следующая известная конструкция. Если Г — связный граф, допускающий вершинно-транзитивную группу автоморфизмов С, и если ф: 1/(Г) У (Г) — накрывающее отображение связного графа Г на граф Г такое, что соответствующая этому отображению накрывающая группа С := {д € АЫ (Т): фд € Сф} группы С вершинно-транзитивна, то множество слоев, а : — {ф~1{х): х Е У (Г)} есть система импримитивности Си ф индуцирует изоморфизм (р графа V/сг на Г такой, что (рС7^" 1 — вершинно-транзитивная подгруппа группы С. Следовательно, Г являетсясимметрическим расширением Г посредством Д, где, А — подграф графа Г, порожденный некоторым слоем из а.

3) Для ряда важных классов связных бесконечных локально конечных вершинно-симметрических графов были получены описания, имеющие, по существу, следующий вид: графы из рассматриваемого класса являются в точности С-симметрическими расширениями некоторых известных графов Г посредством конечных графов, где — некоторые заданные группы автоморфизмов графов Г. Такого вида описания были получены, например, для графов с полиномиальным ростом (см. [3]), для графов с рекуррентным случайным блужданием (см. [4]) и для графов с вершинно-транзитивной группой ограниченных автоморфизмов (см. [5]). Изучение таких О-симметрических расширений графов Г посредством конечных графов является, следовательно, более детальным исследованием этих классов. Определенный интерес представляет в связи с этим изучение симметрических расширений бесконечных локально конечных графов посредством конечных графов.

4) Если Г — симметрическое расширение графа Г посредством графа Д, то граф Г можно интерпретировать «кристаллографически» как граф Г, у которого вершины наделены внутренней структурой вида Д (такие наделенные внутренней структурой вершины графа Г выступают как «молекулы» вида Д), причем эти внутренние структуры вершин графа Г согласуются со структурой Г так, что вся получающаяся в результате конструкция Г (вершины Г выступают при этом как «атомы») симметрична (т.е. граф Г допускает вершинно-транзитивную группу автоморфизмов, отображающую «молекулы» на «молекулы»). В связи с этим симметрические расширения семерных решеток Ас1 посредством конечных графов могут представлять интерес для «молекулярной» кристаллографии.

5) В некоторых физических теориях (см., например [6],) пространство-время наряду с (1 «обычными размерностями» имеет несколько «компактифицированных размерностей». В качестве трансляционно-однородных дискретных аппроксимаций такого пространства-времени могут выступать Ап^А^-симметрические расширения ¿-¿—мерной решетки А<1 посредством конечных графов, где АиЬо (Асг) — группа всех сдвигов, т. е. «параллельных переносов», решетки Л° (Под трансляционной однородностью здесь понимается возможность перемещения любой вершины в любую другую вершину автоморфизмом, индуцирующим сдвиг Л^, т. е. трансляцию на «обычных размерностях» пространства-времени.) В связи с этим представляют интерессимметрические расширения ¿—мерных решеток А (1, посредством конечных графов.

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

Цель диссертационной работы состоит в.

— построении примеров локально конечных графов, допускающих бесконечное число симметрических расширений посредством конечного графа;

— исследовании вопроса о конечности числа симметрических и АЫо (А (1)-симметрических расширений ¿—мерной решетки посредством конечного графа;

— построении всех Лп^о (Лсг)-симметрических расширений ¿—мерной решетки посредством конечного графа, А для некоторых представляющих интерес с1 и А.

Полученные в работе результаты носят теоретический характер. Они могут представлять интерес для теории групп и теории графов, а также могут быть использованы в кристаллографии и в физике (в теории струн). Основные результаты работы являются новыми. Они опубликованы в работах [11]—[20]. Работы [11]-[17], [20] выполнены в нераздельном соавторстве с В. И. Трофимовым.

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

Используемые в работе обозначения, в основном, стандартны. Если Г — граф и X — некоторое подмножество множества его вершин, то через {Х)т обозначается подгаф графа Г, порожденный множеством X. Для графа Г и разбиения, а множества вершин графа Г через где х — вершина графа Г, обозначается подмножество из а, содержащее х. Если д — автоморфизм графа Г, сохраняющий <т, то да — автоморфизм графа Г/сг, индуцируемый д. Если д — автоморфизм графа Г и X —^{-инвариантное} множество вершин графа Г, то дх — подстановка на X, индуцируемая д. Через Т (х) обозначается окрестность вершины х графа Г.

Для произвольного целого положительного числа д связный граф Г называется симметрическим д-расширением графа Г (соответственно, С-сгш-метрическим д-расширением графа Г, где (7 — группа автоморфизмов графа Г), если существуют такая вершинно-транзитивная группа С автоморфизмов графа Г и такая система импримитивности, а группы С на 1/(Г) с блоками порядка д, что найдется изоморфизм ср графа Г/сг на граф Г (соответственно, найдется изоморфизм <р графа Г/сг на граф Г, для которого срС^" 1 = С). При этом говорят, что Г — симметрическое (соответственно, (7-симметрическое)^{-расширение} графа Г, реализуемое С, и, (р. Если в приведенном выше определении симметрического (соответственно, С-симметрического)^{-расширения} графа Г отказаться от условия связности графа Г, то получим определение обобщенного симметрического (соответственно, О-симметрического)^{-расширения} графа Г (реализуемого С, сг,.

Ч>).

Если в данном выше определении симметрического (соответственно, симметрического)^{-расширения} графа Г потребовать, чтобы, а можно было выбрать со следующим дополнительным свойством: для произвольной вершины х графа Г каждый блок системы импримитивности сг, смежный в графе Г/сг с ха, содержит в точности одну смежную с х вершину, то получим определение накрывающего симметрического (соответственно, накрывающего й-симметрического, где й — группа автоморфизмов графа Г) д-расширения графа Г. Если же вместо этого потребовать, чтобы <т можно было выбрать со следующим более слабым свойством: каждая вершина х графа Г смежна не более, чем с одной вершиной из произвольного не содержащего х блока системы импримитивности <т, то получим определение неразветвленного симметрического (соответственно, неразветвленного G-симметрического, где G — группа автоморфизмов графа Г) д-расширения графа Г. (Когда говорится, что накрывающее (соответственно, неразветв-ленное) симметрическое (соответственно, (^-симметрическое) д-расширение графа Г реализуется G, а, ср, то подразумевается, что, а обладает указанным дополнительным свойством.).

Под ¿—мерной решеткой Ad, где d — целое положительное число, понимается граф, вершинами которого являются все упорядоченные наборы (ai,., cid) из d целых чисел, и две вершины (а'1?., a’d) и (а'{,., a?) смежны тогда и только тогда, когда.

К — а!{ | +. + | a’d- = 1.

Для d-мерной решетки Ad и 1 < j < d мы полагаем Prj: V (Ad) —Z, Pr j ((ai, a2,., ud)) = uj.

Сдвигом решетки Ad называется ее автоморфизм, который переводит произвольную вершину (ai,., a?) в вершину (ai + k,., a? + k?) для некоторых фиксированных целых чисел ki,., k?. Для каждого 1 < г < d через U обозначается сдвиг решетки Ad для которого кг = 1 ж к:3 = 0 для всех j G {1,., (?}{?}. Через Auto (Ad) обозначается подгруппа группы автоморфизмов решетки Ad, состоящая из всех ее сдвигов. Для произвольного целого положительного числа g, таким образом, связный граф Г называется обобщенным симметрическим (соответственно, обобщенным AutQ (Ad)~ симметрическим) g-расширением решетки Ad, если существуют такая вер-шинно-транзитивная группа G автоморфизмов графа Г и такая система импримитивности, а группы G на У (Г) с блоками порядка g, что найдется изоморфизм ip графа Т/а на решетку Ad (соответственно, найдется изоморфизм ip графа Т/а на решетку Ad, для которого.

Напомним, что для произвольного связного графа Е через AutoCE) обозначается группа всех его ограниченных автоморфизмов, т. е. таких автоморфизмов g, что расстояния в графе Е между х и д (х), где х пробегает множество всех вершин графа Е, ограничены в совокупности. (Введенное выше обозначение АиЬо (Ал) согласуется с этим определением.) Согласно [5, следствие 2(1)] для связного локально конечного графа Е множество Т (АЫо (Е)) всех его ограниченных автоморфизмов конечного порядка является (нормальной) подгруппой группы АиЬ (Е). При этом, если АиЬо (Е) — вершинно-транзитивна, то согласно [5] система импримитивности, а группы АиЬ{Е) на ^(Е), состоящая из Т (А^о (Е))-орбит, имеет конечные блоки и АиЬо (Е)а = Zd для некоторого целого неотрицательного числа ?.

Как показано в [1], если Г — Л^о (Лсг)-симметрическое^{-расширение} решетки А6, для некоторых целых положительных чисел с1 и д, реализуемое С, а, (р, то блоки, а являются Т (АиЬо (Г))-орбитами на У" (Г) (и, следовательно, а однозначно определена), а Г является Лг^Л^-симметрическим д-рас-ширением решетки Л^, реализуемым АиЬ0(Г), с, р. В связи с этим разбиение, а множества У (Г), состоящее из Т (АиЬо (Т))-офит на У (Г), называется соответствующей Г (как Агг^о (Лсг)-симметрическому д-расширению решетки А*) системой блоков.

В главе 1 доказывается существование связного локально конечного графа Г и конечного графа, А таких, что имеется бесконечное число симметрических расширений Г посредством А. Более того, в главе 1 строится весьма широкий класс локально конечных графов Г, имеющих бесконечное число накрывающих симметрических расширений посредством одного и того же конечного графа А. Для этого в параграфе 1.1 доказывается (см. теорема 1.1.1), что если, А — конечно порожденная группа и В — ее центральная подгруппа, являющаяся свободной абелевой группой счетного ранга, то в случае ограниченности порядков всех конечных подгрупп группы А/В в качестве графа Г можно взять некоторый граф Кэли группы А/В. В параграфе 1.2 с использованием результатов комбинаторной теории групп показывается, что группа, А и ее центральная подгруппа В с требуемыми в теореме 1.1.1 свойствами могут быть выбраны так, что А/В изоморфна произвольной свободной разрешимой группе ступени разрешимости п > 1 с й > 1 свободными порождающими (см. пример 1.2.1- используется [7, теорема А]) или изоморфна определенного вида периодической группе и даже группе, все собственные подгруппы которой имеют фиксированный простой порядок (см. пример 1.2.2- используется [8, параграфы 25, 27, 29, 31]).

Глава 2 посвящена рассмотрению вопроса о конечности числа симметрических и Аи? о (Л^)-симметрических^{-расширений} ¿—мерной решетки Л^. Она состоит из трех параграфов.

В параграфах 2.1 и 2.2 наш подход к исследованию вопроса о конечности числа симметрических и Аг^о (Л^)-симметрических д-расширений ¿-¿—мерной решетки А (1 основывается на проверке выполнения для них следующего условия [пь ., п^-периодичности. Пусть Г — обобщенное симметрическое q-расширение решетки Аа, где с (ид — целые положительные числа, реализуемое С, сг, (р. Скажем, что (Г, <т, <р>) удовлетворяет условию [тгх,., п^-пери-одичности, где щ,., п^ — целые положительные числа, если существуют такие 01,., д<1 € АиЬ{Г), сохраняющие разбиение сг, что [д^, д^} — 1 для всех 1 < г < 3 5: ^ и (Рд^Р" 1 = ¿-Г Для всех 1 < г < <1.

Теорема 2.1.1 утверждает, что для доказательства конечности какого-либо множества симметрических^{-расширений} решетки А'1 достаточно доказать возможность реализовать каждое Г из этого множества такими С, сг, <р, что (Г, сг, (р) удовлетворяет условию [щ,., п^-периодичности для некоторых фиксированных целых положительных чисел щ,., щ. Теорема 2.1.1 используется в параграфах 2.1 и 2.2 для доказательства конечности числа (обобщенных) симметрических и А^о (Л^)-симметрических^{-расширений} решетки А^ в ряде представляющих интерес случаев (см. следствия 2.1.2, 2.1.3, 2.2.1, 2.2.2). Для доказательства этих результатов используется, кроме того, теорема 2.1.2, которая утверждает, что если Г — обобщенное симметрическое д-расширение решетки АЛ для некоторых целых положительных чисел (¿-ид, реализуемое сг, <р, и группа С имеет конечный стабилизатор вершины х графа Г, то (Г, сг, (р) удовлетворяет условию [щ, .,^{-периодичности} для подходящих П1,. На основании теоремы 2.1.1 и теоремы 2.1.2 в параграфе 2.1 доказывается конечность числа неразветвленных симметрических^{-расширений} решетки Ас1 для произвольных целых положительных чисел с? и д (см. следствие 2.1.3). Напомним, что согласно главе 1 у локально конечного вершинно-симметрического графа, вообще говоря, может быть бесконечное число даже накрывающих симметрических расширений посредством фиксированного конечного графа.

Основным результатом параграфа 2.2 является доказательство конечности числа АиЬо (Л^-симметрических д-расширений решетки для произвольного целого положительного числа? и произвольного простого числа д (см. следствие 2.2.2- остается, однако, открытым вопрос о конечности числа Л^о (А?г)-симметрических д-расширений решетки Аа для произвольных целых положительных чисел ¿-ид). Этот результат получается из теоремы 2.2.1 с использование теоремы 2.1.1. Напомним, что группа подстановок называется квазипримитивной, если каждая ее неединичная нормальная подгруппа транзитивна. Теорема 2.2.1 утверждает, что если Г — АЫо (Аа)~ симметрическое д-расширение решетки Л^, реализуемое С, а, , причем стабилизатор в С блока из, а индуцирует на этом блоке квазипримитивную группу, то (Г, сг, (р) удовлетворяет условию [пь ., щ]-периодичности, где Щ < (д!)г1 Для всех 1 < г < ?. В силу теоремы 2.1.1, чтобы получить отсюда следствие 2.2.2, достаточно заметить, что транзитивная группа подстановок простой степени является квазипримитивной.

В параграфе 2.3 получен критерий конечности множества симметрических д-расширений 2-мерной решетки Л2 для целого положительного числа д (теорема 2.3.3). На основе этого критерия получено обобщение следствия 2.1.3 в случае 2-мерной решетки (см. следствие 2.3.1). А именно, доказана конечность числа таких графов Г, являющихся АиЦ{А?)-симметрическими д-расширениями решетки Л2, что для соответствующей Г (как АиЬо (Л2)-симметрическому д-расширению Л2) системы блоков о и для некоторых х 6.

Г) и у е Т/^ГДж0″ выполняется условие {г е уа: {х, г} е ^(Г)}| = 1. Кроме того, этот критерий используется в главе 4 при получении описания Аи? о (Л2)-симметрических 4-расширений 2-мерной решетки Л2.

Наряду с вопросом о конечности числа симметрических и Аг^Л^-сим-метрических д-расширений ¿—мерной решетки Аа интерес представляет также описание всех (обобщенных) Аг/^Л^-симметрических д-расширений ¿—мерной решетки Л^ для фиксированных (как правило, небольших) ¿-ид.

В главе 3 работы получено такое описание для А^о (Лй)-еимметрических 2-расширений решетки где? — произвольное целое положительное число. В параграфе 3.1 рассмотрен случай? < 2, а в параграфе 3.2 — случай? > 2. В качестве следствия этого описания в параграфе 3.2 получена формула для числа А^о (Лсг)-симметрических 2-расширений решетки Аа (см. следствие 3.2.1).

Глава 4 работы посвящена описанию Лг^о (Л^)-симметрических д-расши-рений решетки Ad для небольших d и q. Она состоит из трех параграфов.

В параграфе 4.1 получены список всех обобщенных Auto (Л1)-симметрических 3-расширений решетки Л1 (6 графов) и список всех обобщенных Аи? о (Л2)-симметрических 3-расширений решетки Л2 (32 графа).

Параграфы 4.2 и 4.3 посвящены описанию Лг^с^Л^-симметрических 4-расширений решетки Ad для d = 1 и d = 2. В параграфе 4.2 приводится список всех обобщенных Л^о (Л1)-симметрических 4-расширений решетки Л1 (34 графа) и доказывается теорема 4.2.1, касающаяся групп автоморфизмов Аг^о (Л2)-симметрических 4-расширений решетки А2 (из которой с учетом теоремы 2.3.3) вытекает конечность числа Ли^о (А2)-симметрических 4-расширений решетки Л2). В параграфе 4.3 с использованием теоремы 4.2.1 получен список всех обобщенных Лг^о (Л2)-симметрических 4-расширений решетки Л2 (517 графов).

1. Trofimov V.1. Symmetrical extensions of graphs and some other topics in graph theory related with group theory // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 4. С. 316−320.

2. Imrich W., Klavzar S. Product Graphs: Structure and Recognition // New-York et. al.: John Wiley and Sons, Inc., 2000. 358 p.

3. Трофимов В. И. Графы с полиномиальным ростом // Изв. АН СССР. Сер. математическая. 1985. Т. 51, № 2. С. 405−417.

4. Woess W. Topological groups and reccurrence of quasitransitive graphs // Rend. Sem. Mat. Milano. 1996. Vol. 64. P. 185−213.

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

6. Грин М., Шварц Дж., Виттен Э. Теория суперструн Т. 1, 2 // Москва: Мир, 1990.

7. Baumslag G., Strebel R., Thomson M. On the multiplicator of F/jcR // Journal of Pure and Applied Algebra 1980. Vol. 16, № 2. P. 121−132.

8. Ольшанский А. Ю. Геометрия определяющих соотношений в группах // Москва: Наука, 1989. 448 с.

9. Seifter N., Trofimov V.I. Automorphism Groups of Graphs with Quadratic Growth // J. Comb. Theory. Ser. B. 1997. Vol. 71, № 2. P. 205−210.

10. Харари Ф. Теория графов // Москва: Мир, 1973. 302 с. РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

11. Неганова, Е.А. Лг^А^-симметрические 2-расширения решеток Ad / Е. А. Неганова, В. И. Трофимов // Проблемы теоретич. и прикл. математики: тез. докл. 41-й Всерос. мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2010. С. 64−70.

12. Неганова, Е.А. О симметрических g-расширениях 2-мерной решетки / Е. А. Неганова, В. И. Трофимов // Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16, № 3. С. 199−209.

13. Неганова, Е.А. О симметрических расширениях графов / Е. А. Неганова, В. И. Трофимов // Международная конференция, посвященная 70-летию Академика Ю. Л. Ершова: тезисы докладов. Новосибирск, 2010. С. 88.

14. Неганова, Е. А. Симметрические расширения графов / Е. А. Неганова, В. И. Трофимов // Международная алгебраическая конференция, посвященная 70-летию A.B. Яковлева: тезисы докладов. Санкт-Петербург, 2010. С. 51−53.

15. Неганова, Е.А. О симметрических^{-расширениях} решеток / Е. А. Неганова, В. И. Трофимов // Теория групп и ее приложения: труды 8-ой Международной школы-конференции по теории групп, посвященной 75-летию В. А. Белоногова. Нальчик, 2010. С. 186−189.

16. Неганова, Е. А. Конечность числа Aut0{A2) -симметрических 4-расширений решетки А2 / Е. А. Неганова, В. И. Трофимов // Проблемы теоретич. и прикл. математики: тез. докл. 42-й Всерос. мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2010. С. 227−228.

17. Неганова, Е.А. О симметрических 4-расширениях 2-мерной решетки / Е. А. Неганова, В. И. Трофимов //Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 3. С. 242−257.

18. Неганова, Е.А. Ук^о (Л2)-симметрические 4-расширения 2-мерной решетки А2 / Е. А. Неганова // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 4. С. 222−243.

19. Неганова, Е. А. Конечность числа АиЬ о (Л^) -симметрических д-расширений решетки для простого д / Е. А. Неганова, В. И. Трофимов // Проблемы теоретич. и прикл. математики: тез. докл. 43-й Междунар. мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2012. С. 77−78.