Действие группы на графе

[abrogolat]

Давайте под графом договоримся называть конечный ориентированный мультиреберный граф. Мне проще смотреть на это как на отображение $\operatorname{pr}: V \times V \rightarrow E $, где $V$ - множество вершин, $E$ - множество ТИПОВ ребер. При этом на функцию не накладываются никакие ограничения (возможная несимметричность дает направленность, различные значения - мультиреберность).

Пусть теперь задана конечная группа $G$ и её действие на некотором конечном множестве $V$. Возможно ли построить такой граф $A$ с данным множеством вершин $V$, чтобы группа его автоморфизмов $Sym(A)$ совпала с исходной группой $G$? В идеале, чтобы автоморфизмы этого графа как раз совпадали с действиями этой группы.

Я попробвал сделать такую констркцию: выбираем две произвольные вершины $a, b \in V$. Положим $\operatorname{pr} (a, b) = 1$ (впредь я буду обозначать это как $<a, b> = 1$). И положим $\forall g \in G: <g(a), g(b)> = <a, b> = 1$. Продолжим итеративно. То есть если какое-то ребро $<c, d>$ еще не было "раскрашено", то введем новое значение в $E$, в данном случае 2, и положим $<c, d> = 2$. И опять-таки $\forall g \in G: <g(c), g(d)> = <c, d> = 2$. Таким образом за конечное число шагов мы построим требуемый граф.

Так как граф $A$ был построен так, чтобы группа $G$ своим действием сохраняла структуру графа, то очевидно, что $G \subset Sym(A)$. Хотелось бы доказать обратное вложение, если оно вообще верно. Я пытался доказывать следующим образом. Пусть все-таки существует автоморфизм графа $h_0 \notin G$. Тогда возьмем произвольную вершину $a_1 \in V$. Так как $<a_1, a_1> = <h_0(a_1), h_0(a_1)>$, то существует такой $g_0 \in G$, что $g_0 (a_1) = h_0(a_1)$. Положим $h_1 = g_0^{-1} h_0$ - тоже автоморфизм графа, который не лежит в группе $G$. Причем $h_1(a_1) = a_1$. Возьмем другую вершину $a_2$. Так как $<h_1(a_2), h_1(a_1)> = <a_2, a_1>$, то существует такое $g_1 \in G$, что $g_1(a_1) = h_1(a_1) = a_1$, $g_1(a_2) = h_1(a_2)$. И теперь кладем $h_2 = g_1^{-1} h_1$. А следующий шаг у меня уже сделать элементарными методами не получается, что меня, конечно огорчает. Напрашивается использование мультиграфа, но это уже в другую степь.

Буду рад любой помощи!)

[svv]

abrogolat в сообщении #1601967 писал(а):

Мне проще смотреть на это как на отображение $\operatorname{pr}: V \times V \rightarrow E $, где $V$ - множество вершин, $E$ - множество ТИПОВ ребер.

Может быть, ещё проще $V \times V \rightarrow \mathbb N$, где натуральное число (может быть нулём) показывает, сколько рёбер идут (с учётом их ориентации) из начальной в конечную вершину?

Иначе я не понимаю, чем у Вас различаются разные типы рёбер и почему Вы называете граф мультирёберным.

[KhAl]

Пусть $E = G$, $\operatorname{pr}(v, g(v)) = g$. Тогда $\operatorname{Sym}(A) = G$, если действие $G$ эффективно.

P.S. на самом деле нет. Но идея, вроде, неплохая...

-- 22.07.2023, 09:06 --

А, моя итоговая конструкция совпадает с Вашей.

-- 22.07.2023, 09:15 --

Я бы решал эту задачу, рассматривая орбиты $V$ при действии $G$. На каждой орбите поочерёдно делать так, чтобы $h_n$ действовала тривиально на этой орбите и на всех предыдущих.

-- 22.07.2023, 09:22 --

abrogolat в сообщении #1601967 писал(а):

то очевидно, что $G \subset Sym(A)$

Это верно, только если $G$ действует на $V$ эффективно (нет таких $g \in G$, что $\forall v \in V{:}\; g(v) = v$). Иначе вместо вложения (инъективного отображения) $G \to \operatorname{Sym}(A)$ имеем отображение $G \to \operatorname{Sym}(A)$ с нетривиальным ядром.

А если $G$ не должно действовать эффективно, то ничего не мешает взять $V = \emptyset$.

-- 22.07.2023, 09:42 --

Кстати. Только мне удивительно, что ответ на вопрос положительный? Кажется, что для групп автоморфизмов графов должны быть какие-то ограничения, которые не позволяют произвольную группу реализовать как группу автоморфизмов, но это не так.

[KhAl]

Переформулирую вопрос про построенный Вами граф на групповом языке, вдруг придёт групповик и сразу ответит... Пусть $H_1, \dots, H_k$ -- нормальные подгруппы в $G$ и $x_j$ -- элементы $G/H_j$ ($j = 1,\dots,k$) такие, что для любой пары $x_j$, $x_l$ найдётся $g_{jl} \in G$ такое, что $g_{jl} \equiv x_j \pmod {H_j}$ и $g_{jl} \equiv x_l \pmod {H_l}$. Правда ли, что найдётся $g \in G$ такое, что $g \equiv x_j \pmod {H_j}$ для всех $j = 1,\dots,k$?

-- 22.07.2023, 11:11 --

Итак, контрпример для Вашего графа:

Группа $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ действует на множестве из шести вершин $V = \{v_1, v_2, u_1, u_2, w_1, w_2\}$. Элемент $(1,0)$ меняет местами $u_1$ с $u_2$, $w_1$ с $w_2$, а $v_1$ и $v_2$ оставляет на месте. Элемент $(0,1)$ меняет местами $v_1$ с $v_2$, $u_1$ с $u_2$, а $w_1$ и $w_2$ оставляет на месте. Элемент $(1,1)$ меняет местами $v_1$ с $v_2$, $w_1$ с $w_2$, а $u_1$ и $u_2$ оставляет на месте.

Автоморфизм Вашего графа, который не задаётся действием элемента $G$: $v_1$ и $v_2$ поменять местами, остальное на месте.

-- 22.07.2023, 11:31 --

Как и любого другого графа на $V$, выдерживающего действие $G$. То есть ответ отрицательный, печально...

[abrogolat]

KhAl в сообщении #1602048 писал(а):

abrogolat в сообщении #1601967 писал(а):

то очевидно, что $G \subset Sym(A)$

Это верно, только если $G$ действует на $V$ эффективно (нет таких $g \in G$, что $\forall v \in V{:}\; g(v) = v$). Иначе вместо вложения (инъективного отображения) $G \to \operatorname{Sym}(A)$ имеем отображение $G \to \operatorname{Sym}(A)$ с нетривиальным ядром.

А если $G$ не должно действовать эффективно, то ничего не мешает взять $V = \emptyset$.

Ну про эффективность действия было действительно важно сказать. Я просто вообще все лично для себя мыслил в контексте $G \subset S_n$. А действие тогда на $n$ точках естественным образом индуцируется с $S_n$.

KhAl в сообщении #1602048 писал(а):

Кстати. Только мне удивительно, что ответ на вопрос положительный? Кажется, что для групп автоморфизмов графов должны быть какие-то ограничения, которые не позволяют произвольную группу реализовать как группу автоморфизмов, но это не так.

Ну для групп автоморфизмов графов действительно нет ограничений. Вы, как я понял, в начале поста построили граф Кэли для группы. Вроде известное утверждение про то, что его группа автоморфизмов совпадает с самой группой. Я это доказывать не умею правда, но там симметрии графа точно не совпадают с (видимо, правым) действием группы (для неабелевых групп, насколько я понимаю). Есть даже более сильноу утверждение - Теорема Фрухта - о том, что всякую конечную группу можно реализовать в виде группы автоморфизмов некоторого ПРОСТОГО графа. Есть даже усиление для бесконечных групп.

KhAl в сообщении #1602064 писал(а):

Итак, контрпример для Вашего графа:

Группа $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ действует на множестве из шести вершин $V = \{v_1, v_2, u_1, u_2, w_1, w_2\}$. Элемент $(1,0)$ меняет местами $u_1$ с $u_2$, $w_1$ с $w_2$, а $v_1$ и $v_2$ оставляет на месте. Элемент $(0,1)$ меняет местами $v_1$ с $v_2$, $u_1$ с $u_2$, а $w_1$ и $w_2$ оставляет на месте. Элемент $(1,1)$ меняет местами $v_1$ с $v_2$, $w_1$ с $w_2$, а $u_1$ и $u_2$ оставляет на месте.

Автоморфизм Вашего графа, который не задаётся действием элемента $G$: $v_1$ и $v_2$ поменять местами, остальное на месте.

-- 22.07.2023, 11:31 --

Как и любого другого графа на $V$, выдерживающего действие $G$. То есть ответ отрицательный, печально...

Огромное спасибо за контрпример! Да... печально. Интересно, в чем здесь дело. В том ли, что вершин слишком много? Просто можно строить все-таки мультиграф, то есть ввести функцию $V \times V \times V \rightarrow E$. В вашем случае её уже будет достаточно, чтобы все-таки зафиксировать все симметрии графа группой $G$ ($<u_1, v_1, w_1> = <u_1, v_2, w_2> = \dots$ но $\neq <u_1, v_2, w_1>$). Правда вроде бы очевидно, что легко аналогично построиь контрпример, для которого и "тринарной" функции не хватит. В то же время, если $|V| = n$, то функции $V^{\times n} \rightarrow E$ хватит точно, но должно существовать минимальное $m$, такое что заданием $V^{\times m} \rightarrow E$ гарантируем $G = Aut(A)$. И вот правда ли тогда, что если $|V| = \min \left\{ n: G \subset S_n \right\}$, то можно ограничиться функцией $V \times V \rightarrow E$ (Или при $|V| \leq |G|$, раз уж для $|V| = |G|$ существует граф Кэли, на котором автоморфизмы действуют транзитивно, а казалось бы такие патологии могут возникать из-за слишком большого количества вершин)?

[abrogolat]

svv в сообщении #1602009 писал(а):

abrogolat в сообщении #1601967 писал(а):

Мне проще смотреть на это как на отображение $\operatorname{pr}: V \times V \rightarrow E $, где $V$ - множество вершин, $E$ - множество ТИПОВ ребер.

Может быть, ещё проще $V \times V \rightarrow \mathbb N$, где натуральное число (может быть нулём) показывает, сколько рёбер идут (с учётом их ориентации) из начальной в конечную вершину?

Иначе я не понимаю, чем у Вас различаются разные типы рёбер и почему Вы называете граф мультирёберным.

Ну это формальности все. Если Вам так удобнее - я ничего не имею против, но для исследования вопросов связанных с симметриями графов от множества типов ребер нужно только то, что это множество. Больше никакие структуры не нужны. Поэтому я ничего не говорю о множестве типов ребер a priori. Ну я как бы могу сказать, что два ребра - это просто новый тип "одного" ребра. Не знаю, стало ли понятнее. Но, повторюсь, это просто обозначения, которые, как мне кажется, обощают понимание. Можно и без них, если угодно.

Обнаружил, что к примеру при рассмотрении действия группы на самой себе справа (слева) можно построить граф по алгоритму описанному мной выше (для неабелевых групп это будет не граф Кэли. Или не для всех неабелевых, а только для тех, у которых все классы сопряженных элемнетов имеют мощность 1. Не силен в теории групп, не знаю, часто ли такое бывает. Но в абелевом случае это так). При этом действие очевидно транзитивно, а значит орбита всего одна. Тогда по формуле орбит: $ |G|/|Stab(v)| = |G(v)| = |V| = |G| $. Значит все стабилизаторы тривиальны. Но тогда можно глянуть мой первый пост, где я рассматриваю "дополнительную симметрию" $h_0 \in Sym(A)$. Если она не тождественная то найдется такая вершина, что $h_0(a) \neq a$. Строим $h_1: h_1(a) = a$. Если теперь $h_1$ - тождественно, то $h_0 = g_0 \in G$ (все обозначения опять-таки из первого сообщения). В противном случае $h_1(b) \neq b$. Но мы можем найти такую $g_1 \in G: g_1(b) = h_1(b), g_1(a) = h_1(a) = a$. То есть $g_1 \in Stab(a) = {e}$. Противоречие.

[B@R5uk]

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

[KhAl]

abrogolat я запишу несколько замечаний, которые до этого опустил для краткости.

1) Ваш граф среди всех графов на $V$, выдерживающих действие $G$, имеет наименьшую группу симметрий. Так что его очень правильно рассматривать.

2) Ваш граф можно описать в двух словах. $\langle a_1, a_2 \rangle = \langle b_1, b_2 \rangle$ т.т.т. $\exists g \in G{:}\; (a_1, a_2) = (g(b_1), g(b_2))$. Обобщается на мультиграфы (то, что Вы называете мультиграфами. Википедия с Вами не согласна...).

3) Я всё-таки смотрю на орбиты $V$ при действии $G$ (я не хотел акцентировать внимание, потому что вдруг есть более простой подход, до которого Вы догадаетесь, но скрывать и тратить Ваше время тоже не стоит...). $H_1$, $H_2$, ..., $H_k$ из предыдущего сообшения это стабилизаторы орбит. В моём примере есть $3$ орбиты, но я начинал именно с подгрупп и строил по тройке подгрупп нужный граф (то есть, я сначала нашёл контрпример к "групповому" утверждению).

Если рассматривать мультиграфы, двойку в "групповом" утверждении нужно заменить на наибольшее число концов мультиребра.

4) Домножим мой пример ещё на $n$ копий $\mathbb{Z}/2\mathbb{Z}$ и добавим в граф $n$ орбит длины $2$, на которые эти копии будут действовать (каждая на свою, игнорируя остальные). Тогда группа будет порядка $4 \cdot 2^n$, а число вершин $6 + 2n$.

5) Несмотря на (4), вопрос про наименьшее возможное число вершин интересен. Так же можно минимизировать граф и другими способами. Например, можно из $V$ выкидывать орбиты так, чтобы действие $G$ осталось эффективным. Можно ввести на $V$ отношение эквивалентности, выдерживающее действие $G$, и проафакторизовать по нему так, чтобы действие $G$ осталось эффективным (это не то же самое, что стянуть часть орбит в точку. Например, можно отождествить друг с другом две "одинаковые" орбиты). И вот можно спросить, что получится, если $V$ нельзя уменьшить этими двумя способами... Этот подход хорош тем, что это ограничение (вроде как) можно перевести на групповой язык, задав ограничения на подгруппы $H_1$, $H_2$, ..., $H_k$ выше. Но всё становится слооожно, я не знаю, как там контрпримеры искать, а уж тем более -- доказывать...

6) С B@R5uk согласен; у меня самого не хватает мозга и прямых рук, чтобы это делать.

-- 23.07.2023, 21:43 --

Цитата:

Или не для всех неабелевых, а только для тех, у которых все классы сопряженных элемнетов имеют мощность 1

Такая группа абелева. Вообще, класс сопряжённости $g$ совпадает с $\{g\}$ ровно тогда, когда $g$ централен (коммутирует со всеми элементами группы).

-- 23.07.2023, 21:45 --

Цитата:

Но тогда можно глянуть мой первый пост, где я рассматриваю "дополнительную симметрию" $h_0 \in Sym(A)$. Если она не тождественная то найдется такая вершина, что $h_0(a) \neq a$. Строим $h_1: h_1(a) = a$. Если теперь $h_1$ - тождественно, то $h_0 = g_0 \in G$ (все обозначения опять-таки из первого сообщения). В противном случае $h_1(b) \neq b$. Но мы можем найти такую $g_1 \in G: g_1(b) = h_1(b), g_1(a) = h_1(a) = a$. То есть $g_1 \in Stab(a) = {e}$. Противоречие.

Лучше. Любой автоморфизм Вашего графа на каждой орбите действует как домножение на какой-то $g \in G$, вопрос только в согласованности $g$ для разных орбит. Тут Вы рассматриваете случай, когда орбита всего одна...

[abrogolat]

KhAl,

2) Могу сразу поблагодарить за исправление в терминологии. Образованные люди действительно называют мои "мультиграфы" гиперграфами. Впредь постараюсь делать так же.

4) Простая арифметика. Но существенная. Ещё раз спасибо Вам.

5) Я тоже думаю в том числе в этом направлении. Правда совсем неудобно мне мыслить в терминах общей Теории Групп. Так что может я и не продвинусь далеко, но если будет что-то более сформированное, обязательно напишу.

6) Вот мне бы лично хотелось научиться такие вещи на комп ставить. Есть же даже системы компьютерной алгебры типа GAP, которые примерно для таких задач были созданы. Но не сейчас, увы...

[B@R5uk]

Вообще, брутфорсить можно не только на компьютере, но и в ручную; что я, собственно и имел в виду в данном случае. Идея в том, чтобы на пальцах прочувствовать, что происходит в задаче, а потом уже пытаться эти результаты обобщать.

Можно, кстати, к этому вопросу и с другой стороны подойти: пытаться рассматривать разные типы простых графов и смотреть какие группы из них получаются. Например, правильные многоугольники вполне себе можно считать двунаправленными кольцевыми графами с равными единичными ребрами. А по определению диэдральной группы она и является группой симметрий (автоморфизмов) таких многоугольников (графов). Вот, для целого класса групп вопрос решён положительно.

-- 24.07.2023, 09:41 --

Ещё такое наблюдение. В постановке задачи нигде не сказано, что граф должен быть связным. Отсюда сразу следует, что если у нас есть два графа $\mathfrak{G}_1$ и $\mathfrak{G}_2$, порождающие соответственно группы $G_1$ и $G_2$, то группа $G_1\times G_2$ порождается простым объединением исходных графов. Единственное, для случая $G^2$ рёбра объединяемых копий надо сделать различными, иначе у результирующего графа будет группа автоморфизмов $G^2\rtimes Z_2$ или что-то в этом духе.

-- 24.07.2023, 09:48 --

О! Ещё, если в графе N вершин и 0 рёбер, то группой автоморфизмов такого графа будет, очевидно, $S_N$, не здорово ли?

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

[abrogolat]

KhAl в сообщении #1602226 писал(а):

Любой автоморфизм Вашего графа на каждой орбите действует как домножение на какой-то $g \in G$...

KhAl, а Вы бы не могли прокомментировать, откуда следует, что на каждой орбите автоморфизмы - действия группы? Просто тогда получается, что во всех случаях, когда орбита одна, $Sym(A) = G$. Что очень приятно, как мне кажется.

[KhAl]

когда орбита одна, то и граф один, он задаётся левым регулярным действием, $V = G$ и $g(v) = gv$. тривиальный случай.

а откуда следует, мне лень писать. проверка в лоб.

[abrogolat]

KhAl в сообщении #1602477 писал(а):

когда орбита одна, то и граф один, он задаётся левым регулярным действием, $V = G$ и $g(v) = gv$. тривиальный случай.

Есть просто, к примеру, $G=S_n$, которая транзитивно действует на $n$ точках. Тут вроде тоже орбита одна, но $V \neq G$.

[KhAl]

да, я ошибся. насчёт действия на каждой орбите -- не знаю, наверное всё-таки правда...

-- 26.07.2023, 11:39 --

или нет

-- 26.07.2023, 12:06 --

поменяю чуть-чуть обозначения, мне так удобней. вот пример, когда орбита одна.

рассмотрим четверную группу Клейна $V_4 = \{1, a_1, a_2, a_3\}$, где $a_1^2 = a_2^2 = a_3^2 = 1$, $a_1a_2 = a_3$, $a_2a_3 = a_1$, $a_1a_3 = a_2$ (та же $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$).

$\operatorname{Aut}(V_4) \sim S_3$ и можно составить полупрямое произведение $V_4 \rtimes S_3$.

Рассмотрим множество из шести элементов $\{u_1, v_1; u_2, v_2; u_3, v_3\}$. Полупрямое произведение будет действовать так: $a_i$ меняет местами $u_k$ с $v_k$, $u_j$ с $v_j$, где $i \notin \{k, j\}$; $S_3$ переставляет индексы как обычно (надо проверить, что это отображение, заданное на двух подгруппах, продолжается до действия группы. я в этом уверен не на 100%, но мне лень). Походу, для Вашего графа $A$ $\operatorname{Sym}(A)$ состоит из $48$ элементов, а группа -- всего из $24$. Я, кстати, не представляю, как эта группа может эффективно действовать на пяти точках, шесть это уже мало...

-- 26.07.2023, 12:19 --

abrogolat (чтоб уведомление пришло, а то из-за редактирования не видно, что я что-то новое написал)

Изменю конструкцию сверху, чтобы техническая часть упростилась. Можно начать с графа $A$ на шести вершинах $\{u_1, v_1; u_2, v_2; u_3, v_3\}$ где $u_k$ с $v_k$ И $v_k$ с $u_k$ соединены рёбрами типа $m$, а все остальные пары -- рёбрами типа $p$. $\operatorname{Sym}(A)$ состоит из $48$ элементов (сначала переставляем индексы (6 вариантов), потом для каждого индекса переставляем или не переставляем $u_k$ с $v_k$ (8 вариантов)). Далее, положим $t(u_k) = 0$ и $t(v_k) = 1$. В $\operatorname{Sym}(A)$ можно выделить подгруппу $G$ преобразований, сохраняющих $t(u_1) + t(u_2) + t(u_3) \pmod 2$, она порядка $24$. И вот симметрии любого графа на тех же вершинах, выдерживающего действие $G$, содержат $\operatorname{Sym}(A)$.

[KhAl]

Цитата:

преобразований, сохраняющих $t(u_1) + t(u_2) + t(u_3) \pmod 2$

в смысле, преобразования $f$ такие, что $t(f(u_1)) + t(f(u_2)) + t(f(u_3)) \equiv 0 \pmod 2$. Не мгновенно очевидно, почему такие преобразования образуют подгруппу, ну и ладно.

-- 26.07.2023, 12:45 --

Кстати, можно уменьшить порядок подгруппы до $12$, если рассмотреть подгруппу преобразований, сохраняющих $t(u_1) + t(u_2) + t(u_3)$ и при этом переставляющих индексы $1, 2, 3$ строго по циклу (тогда эта группа $V_4 \rtimes \mathbb{Z}/3\mathbb{Z} < V_4 \rtimes S_3$). Я взял порядок $24$, потому что тогда больше шансов, что она на пяти вершинах эффективно не действует.

-- 26.07.2023, 12:55 --

Чёрт, эта группа из $24$ элементов изоморфна $S_4$. А подгруппа порядка $12$ изоморфна $A_4$... Но по крайней мере убиранием орбит (она одна) или факторизацией граф уменьшить нельзя.

-- 26.07.2023, 13:20 --

Заменив двойку на тройку, можно добиться действия $(\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}) \rtimes \mathbb{Z}/3\mathbb{Z}$ на множестве из $9$-и элементов, которое служит контрпримером, если потребовать минимальное число вершин, причём орбита всего одна. Путь к этому был довольно окольный, так что наврное есть более простой пример -- проще всего перебирать подгруппы в $S_n$, $n \leqslant 9$. Опишу это действие как подгруппу в $S_9$. Она порождена $(123)(456)$, $(456)(789)$ (левая часть полупрямого произведения) и $(167)(258)(349)$ (правая часть полупрямого произведения). В $S_8$ эта группа не вкладывается, потому что порядок $S_8$ не делится на $27$.

-- 26.07.2023, 13:29 --

Всё очень неподробно написано, так что спрашивайте, если что