Граф Кэли

Граф Кэли свободной группы с двумя образующими a и b

Семейства графов, определенные своими автоморфизмами
дистанционно-транзитивный	→	дистанционно-регулярный	←	сильно регулярный
↓
симметричный (дугопереходный)	←	t -транзитивен, t ≥ 2		кососимметричный
↓
(если подключен) вершинно- и реберно-транзитивен	→	реберно-транзитивный и регулярный	→	краево-транзитивный
↓		↓		↓
вершинно-транзитивный	→	обычный	→	(если двусторонний) бирегулярный
↑
Граф Кэли	←	нуль-симметричный		асимметричный

В математике граф Кэли , также известный как цветовой граф Кэли , диаграмма Кэли , групповая диаграмма или цветовая группа , — это граф , который кодирует абстрактную структуру группы . Его определение предложено теоремой Кэли (названной в честь Артура Кэли ) и использует указанный набор генераторов для группы. Это центральный инструмент в комбинаторной и геометрической теории групп . Структура и симметрия графов Кэли делают их особенно хорошими кандидатами для построения графов-расширителей .

Определение

Позволять $G$ быть группой и $S$ быть генератором множества $G$. Граф Кэли $\Gamma =\Gamma (G,S)$ представляет собой с раскрашенными ребрами, ориентированный граф построенный следующим образом:

• Каждый элемент $g$ из $G$ назначается вершина: набор вершин $\Gamma$ отождествляется с $G.$
• Каждый элемент $s$ из $S$ присвоен цвет $c_{s}$.
• Для каждого $g\in G$ и $s\in S$, имеется направленный край цвета $c_{s}$ из вершины, соответствующей $g$ к тому, который соответствует $gs$.

Не каждая конвенция требует этого $S$ сгенерировать группу. Если $S$ это не генераторная установка для $G$, затем $\Gamma$ несвязен порожденной , и каждый связный компонент представляет собой смежный класс подгруппы, $S$.

Если элемент $s$ из $S$ является своей собственной инверсией, $s=s^{-1},$ тогда это обычно представляется ненаправленным краем.

Набор $S$ часто предполагается конечным, особенно в геометрической теории групп , что соответствует $\Gamma$ будучи локально конечным и $G$ быть конечно порожденной.

Набор $S$ иногда считается симметричным ( $S=S^{-1}$ группы ) и не содержащий элемент идентификации . В этом случае неокрашенный граф Кэли можно представить как простой неориентированный граф .

Примеры

• Предположим, что $G=\mathbb {Z}$ — бесконечная циклическая группа и множество $S$ состоит из стандартного генератора 1 и обратного ему (−1 в аддитивных обозначениях); тогда граф Кэли представляет собой бесконечный путь.
• Аналогично, если $G=\mathbb {Z} _{n}$ — конечная циклическая группа порядка $n$ и набор $S$ состоит из двух элементов, стандартного генератора $G$ и обратного, то граф Кэли — это цикл $C_{n}$. В более общем смысле, графы Кэли конечных циклических групп являются в точности циркулянтными графами .
• Граф Кэли прямого произведения групп (с декартовым произведением порождающих наборов в качестве порождающего набора) является декартовым произведением соответствующих графов Кэли. Таким образом, граф Кэли абелевой группы $\mathbb {Z} ^{2}$ с набором образующих, состоящим из четырех элементов $(\pm 1,0),(0,\pm 1)$ это бесконечная сетка на плоскости $\mathbb {R} ^{2}$, а для прямого произведения $\mathbb {Z} _{n}\times \mathbb {Z} _{m}$ с аналогичными генераторами граф Кэли представляет собой $n\times m$ конечная сетка на торе .

Граф Кэли группы диэдра $D_{4}$ на двух генераторах a и b

График Кэли $D_{4}$, на двух генераторах, оба самообратных

• Граф Кэли группы диэдра $D_{4}$ на двух генераторах $a$ и $b$ изображен слева. Красные стрелки обозначают композицию с $a$. С $b$ является самоинверсным , синие линии обозначают композицию с $b$, являются ненаправленными. Следовательно, граф смешанный: у него восемь вершин, восемь стрелок и четыре ребра. Таблица Кэли группы $D_{4}$ можно получить из групповой презентации $$\langle a,b\mid a^{4}=b^{2}=e,ab=ba^{3}\rangle .$$ Другой граф Кэли $D_{4}$ показано справа. $b$ по-прежнему является горизонтальным отражением и представлен синими линиями, а $c$ представляет собой диагональное отражение и представлено розовыми линиями. Поскольку оба отражения самообратны, граф Кэли справа совершенно неориентирован. Этот график соответствует представлению $$\langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .$$
• Граф Кэли свободной группы с двумя образующими $a$ и $b$ соответствующий набору $S=\{a,b,a^{-1},b^{-1}\}$ изображено в верхней части статьи, с $e$ будучи личностью. Путешествие по ребру вправо представляет собой правильное умножение на $a,$ при движении по ребру вверх соответствует умножению на $b.$ Поскольку свободная группа не имеет отношений , граф Кэли не имеет циклов : это 4- регулярное бесконечное дерево . Это ключевой ингредиент в доказательстве парадокса Банаха-Тарского .
• В более общем смысле решетка Бете или дерево Кэли — это граф Кэли свободной группы на $n$ генераторы. Презентация ​ группы $G$ к $n$ генераторов соответствует сюръективному гомоморфизму свободной группы на $n$ генераторы в группу $G,$ определение отображения дерева Кэли в граф Кэли $G$. интерпретируя графы Топологически как одномерные симплициальные комплексы , односвязное бесконечное дерево является универсальным покрытием графа Кэли; а ядром отображения является фундаментальная группа графа Кэли.

Часть графа Кэли группы Гейзенберга. (Раскраска предназначена только для наглядности.)

• Граф Кэли дискретной группы Гейзенберга $$\left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}$$ изображено справа. Генераторы, используемые на картинке, представляют собой три матрицы $X,Y,Z$ задаются тремя перестановками 1, 0, 0 для записей $x,y,z$. Они удовлетворяют отношения $Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY$, что также можно понять по картинке. Это некоммутативная бесконечная группа, и, несмотря на то, что граф Кэли является трехмерным пространством, он имеет четырехмерный рост объема .

График Кэли Q8, показывающий циклы умножения на кватернионы i , j и k

Характеристика

Группа $G$ действует на себя умножением слева (см. теорему Кэли ). Это можно рассматривать как действие $G$ на его графе Кэли. Явно элемент $h\in G$ отображает вершину $g\in V(\Gamma )$ до вершины $hg\in V(\Gamma ).$ При этом действии сохраняется множество ребер графа Кэли и их цвет: ребро $(g,gs)$ отображается на краю $(hg,hgs)$, оба имеют цвет $c_{s}$. Фактически, все автоморфизмы цветного ориентированного графа $\Gamma$ имеют такую ​​форму, так что $G$ изоморфна симметрии группе $\Gamma$.

Левое умножение группы на себя просто транзитивно , в частности, графы Кэли вершинно-транзитивны . Следующее является своего рода обратным этому:

Теорема Сабидусси - ориентированный граф (немаркированный и неокрашенный). $\Gamma$ является графом Кэли группы $G$ тогда и только тогда, когда оно допускает просто транзитивное действие $G$ автоморфизмами графа (т. е. сохранением множества направленных ребер).

Чтобы восстановить группу $G$ и генераторная установка $S$ из неразмеченного ориентированного графа $\Gamma$, выберите вершину $v_{1}\in V(\Gamma )$ и пометить его идентификационным элементом группы. Затем пометьте каждую вершину $v$ из $\Gamma$ благодаря уникальному элементу $G$ это отображает $v_{1}$ к $v.$ Набор $S$ генераторов $G$ это дает $\Gamma$ как граф Кэли $\Gamma (G,S)$ представляет собой набор меток внешних соседей $v_{1}$. С $\Gamma$ бесцветен, он может иметь больше автоморфизмов направленного графа, чем карты левого умножения, например групповые автоморфизмы $G$ которые переставляют $S$.

Элементарные свойства

• Граф Кэли $\Gamma (G,S)$ существенно зависит от выбора множества $S$ генераторов. Например, если генераторная установка $S$ имеет $k$ элементов, то каждая вершина графа Кэли имеет $k$ входящие и $k$ исходящие направленные ребра. В случае симметричной генераторной установки $S$ с $r$ элементов граф Кэли является регулярным ориентированным графом степени $r.$
• Циклы (или замкнутые обходы ) в графе Кэли указывают на отношения между элементами $S.$ В более сложной конструкции комплекса Кэли группы замкнутые пути, соответствующие отношениям, «заполняются» многоугольниками . Это означает, что задача построения графа Кэли заданного представления ${\mathcal {P}}$ эквивалентно решению задачи слов для ${\mathcal {P}}$.
• Если $f:G'\to G$ является сюръективным групповым гомоморфизмом и образами элементов порождающего множества $S'$ для $G'$ различны, то это индуцирует покрытие графов $${\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),$$ где $S=f(S').$ В частности, если группа $G$ имеет $k$ генераторы, все порядка отличного от 2, и множество $S$ состоит из этих генераторов вместе с их обратными, то граф Кэли $\Gamma (G,S)$ покрыто бесконечным регулярным деревом степени $2k$ соответствующую свободной группе на том же наборе образующих.
• Для любого конечного графа Кэли, рассматриваемого как неориентированный, связность вершин равна как минимум 2/3 степени графа . Если порождающий набор минимален (удаление любого элемента и, если он есть, обратного ему из порождающего набора, остается набор, который не является порождающим), связность вершин равна степени. Связность ребер во всех случаях равна степени.
• Если $\rho _{\text{reg}}(g)(x)=gx$ — леворегулярное представление с $|G|\times |G|$ матричная форма, обозначенная $[\rho _{\text{reg}}(g)]$, матрица смежности $\Gamma (G,S)$ является ${\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(s)]}$.
• Каждый персонаж группы $\chi$ группы $G$ индуцирует вектор матрицы смежности собственный $\Gamma (G,S)$. Соответствующее собственное значение $$\lambda _{\chi }=\sum _{s\in S}\chi (s),$$ который, когда $G$ абелева, принимает вид $$\sum _{s\in S}e^{2\pi ijs/|G|}$$ для целых чисел $j=0,1,\dots ,|G|-1.$ В частности, соответствующее собственное значение тривиального символа (того, который переводит каждый элемент в 1) — это степень $\Gamma (G,S)$, то есть порядок $S$. Если $G$ является абелевой группой, существует ровно $|G|$ символы, определяющие все собственные значения. Соответствующий ортонормированный базис собственных векторов имеет вид $v_{j}={\tfrac {1}{\sqrt {|G|}}}{\begin{pmatrix}1&e^{2\pi ij/|G|}&e^{2\cdot 2\pi ij/|G|}&e^{3\cdot 2\pi ij/|G|}&\cdots &e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}}.$ Интересно отметить, что этот собственный базис не зависит от порождающего набора. $S$.
  В более общем смысле для симметричных генераторных установок возьмем $\rho _{1},\dots ,\rho _{k}$ полный набор неприводимых представлений $G,$ и пусть ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ с набором собственных значений $\Lambda _{i}(S)$. Тогда набор собственных значений $\Gamma (G,S)$ это точно ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ где собственное значение $\lambda$ появляется с кратностью $\dim(\rho _{i})$ за каждое возникновение $\lambda$ как собственное значение $\rho _{i}(S).$

Граф смежности Шрайера

Основная статья: граф смежности Шрайера

Если вместо этого взять вершины как правые смежные классы фиксированной подгруппы $H,$ получается родственная конструкция, граф смежных классов Шрайера , который лежит в основе перечисления смежных классов или процесса Тодда – Кокстера .

Связь с теорией групп

Знания о структуре группы можно получить, изучая матрицу смежности графа и, в частности, применяя теоремы спектральной теории графов . И наоборот, для симметричных порождающих наборов спектральная теория и теория представлений $\Gamma (G,S)$ напрямую связаны между собой: возьмите $\rho _{1},\dots ,\rho _{k}$ полный набор неприводимых представлений $G,$ и пусть ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ с собственными значениями $\Lambda _{i}(S)$. Тогда набор собственных значений $\Gamma (G,S)$ это точно ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ где собственное значение $\lambda$ появляется с кратностью $\dim(\rho _{i})$ за каждое возникновение $\lambda$ как собственное значение $\rho _{i}(S).$

Род . группы — это минимальный род любого графа Кэли этой группы

Геометрическая теория групп

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

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

Свойства расширения

Когда $S=S^{-1}$, граф Кэли $\Gamma (G,S)$ является $|S|$ можно использовать спектральные методы -регулярный, поэтому для анализа свойств расширения графа . В частности, для абелевых групп собственные значения графа Кэли легче вычислимы и определяются выражением ${\textstyle \lambda _{\chi }=\sum _{s\in S}\chi (s)}$ с верхним собственным значением, равным $|S|$, поэтому мы можем использовать неравенство Чигера , чтобы ограничить коэффициент расширения края с помощью спектрального разрыва.

Теорию представлений можно использовать для построения таких расширяющихся графов Кэли в форме свойства Каждана (T) . Имеет место следующее утверждение:

Если дискретная группа $G$ has Kazhdan's property (T), and $S$ представляет собой конечный симметричный порождающий набор $G$, то существует константа $c>0$ в зависимости только от $G,S$ такая, что для любого конечного частного $Q$ из $G$ граф Кэли $Q$ относительно образа $S$ это $c$-расширитель.

Например, группа $G=\mathrm {SL} _{3}(\mathbb {Z} )$ обладает свойством (T) и порождается элементарными матрицами , что дает относительно явные примеры графов-расширителей.

Интегральная классификация

Интегральный граф — это тот, у которого все собственные значения являются целыми числами. Хотя полная классификация целочисленных графов остается открытой проблемой, графы Кэли некоторых групп всегда целочисленны.Используя предыдущие характеристики спектра графов Кэли, заметим, что $\Gamma (G,S)$ является целым тогда и только тогда, когда собственные значения $\rho (S)$ являются целыми для каждого представления $\rho$ из $G$.

Целочисленная простая группа Кэли

Группа $G$ является целочисленно-простым Кэли (CIS), если связный граф Кэли $\Gamma (G,S)$ является целым в точности тогда, когда симметричный порождающий набор $S$ является дополнением подгруппы $G$. Результат Ахмади, Белла и Мохара показывает, что все группы CIS изоморфны $\mathbb {Z} /p\mathbb {Z} ,\mathbb {Z} /p^{2}\mathbb {Z}$, или $\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ для простых чисел $p$. Важно, чтобы $S$ фактически генерирует всю группу $G$ для того, чтобы граф Кэли был связным. (Если $S$ не генерирует $G$, граф Кэли все еще может быть целым, но дополнение $S$ не обязательно является подгруппой.)

На примере $G=\mathbb {Z} /5\mathbb {Z}$, симметричные порождающие множества (с точностью до изоморфизма графов) имеют вид

• $S=\{1,4\}$: $\Gamma (G,S)$ это $5$-цикл с собственными значениями $2,{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}}$
• $S=\{1,2,3,4\}$: $\Gamma (G,S)$ является $K_{5}$ с собственными значениями $4,-1,-1,-1,-1$

Единственные подгруппы $\mathbb {Z} /5\mathbb {Z}$ - это вся группа, тривиальная группа и единственный симметричный порождающий набор $S$ образующий интегральный граф, является дополнением тривиальной группы. Поэтому $\mathbb {Z} /5\mathbb {Z}$ должна быть группой СНГ.

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

Целочисленная группа Кэли

Немного другое понятие - это целая группа Кэли. $G$, в котором каждое симметричное подмножество $S$ создает интегральный график $\Gamma (G,S)$. Обратите внимание, что $S$ больше не нужно генерировать всю группу.

Полный список целых групп Кэли имеет вид $\mathbb {Z} _{2}^{n}\times \mathbb {Z} _{3}^{m},\mathbb {Z} _{2}^{n}\times \mathbb {Z} _{4}^{n},Q_{8}\times \mathbb {Z} _{2}^{n},S_{3}$и дициклическая группа порядка $12$, где $m,n\in \mathbb {Z} _{\geq 0}$ и $Q_{8}$ это группа кватернионов. Доказательство опирается на два важных свойства целых групп Кэли:

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

Нормальные и эйлеровы генераторы

Учитывая общую группу $G$, подмножество $S\subseteq G$ это нормально, если $S$ замкнуто относительно сопряжения элементами $G$ (обобщающее понятие нормальной подгруппы) и $S$ является эйлеровым, если для каждого $s\in S$, набор элементов, образующих циклическую группу $\langle s\rangle$ также содержится в $S$.Результат Го, Лыткиной, Мазурова и Ревина, полученный в 2019 году, доказывает, что граф Кэли $\Gamma (G,S)$ является целым для любого эйлерова нормального подмножества $S\subseteq G$, используя чисто теоретические методы представления.

Доказательство этого результата относительно короткое: учитывая $S$ Эйлерово нормальное подмножество, выберите $x_{1},\dots ,x_{t}\in G$ попарно несопряжены, так что $S$ есть объединение классов сопряженности $\operatorname {Cl} (x_{i})$. Затем, используя характеристику спектра графа Кэли, можно показать собственные значения $\Gamma (G,S)$ даны ${\textstyle \left\{\lambda _{\chi }=\sum _{i=1}^{t}{\frac {\chi (x_{i})\left|\operatorname {Cl} (x_{i})\right|}{\chi (1)}}\right\}}$ захвачены нередуцируемые персонажи $\chi$ из $G$. Каждое собственное значение $\lambda _{\chi }$ в этом наборе должен быть элемент $\mathbb {Q} (\zeta )$ для $\zeta$ примитивный $m^{th}$ корень из единицы (где $m$ должно делиться на порядок каждого $x_{i}$). Поскольку собственные значения являются целыми алгебраическими числами, чтобы доказать их целочисленность, достаточно показать, что они рациональны, и достаточно доказать, что $\lambda _{\chi }$ фиксирован при любом автоморфизме $\sigma$ из $\mathbb {Q} (\zeta )$. Должны быть какие-то $k$ относительно простой для $m$ такой, что $\sigma (\chi (x_{i}))=\chi (x_{i}^{k})$ для всех $i$, и потому что $S$ является одновременно эйлеровым и нормальным, $\sigma (\chi (x_{i}))=\chi (x_{j})$ для некоторых $j$. Отправка $x\mapsto x^{k}$ биективные классы сопряженности, поэтому $\operatorname {Cl} (x_{i})$ и $\operatorname {Cl} (x_{j})$ иметь одинаковый размер и $\sigma$ просто переставляет члены в сумме для $\lambda _{\chi }$. Поэтому $\lambda _{\chi }$ фиксирован для всех автоморфизмов $\mathbb {Q} (\zeta )$, так $\lambda _{\chi }$ является рациональным и, следовательно, целым.

Следовательно, если $G=A_{n}$ представляет собой знакопеременную группу и $S$ представляет собой набор перестановок, заданный формулой $\{(12i)^{\pm 1}\}$, то граф Кэли $\Gamma (A_{n},S)$ является интегральным. (Это решило ранее открытую проблему из « Коуровской тетради» .) Кроме того, когда $G=S_{n}$ является симметричной группой и $S$ - это либо набор всех транспозиций, либо набор транспозиций, включающих определенный элемент, граф Кэли $\Gamma (G,S)$ также является целым.

История

Графы Кэли были впервые рассмотрены для конечных групп Артуром Кэли в 1878 году. Макс Ден в своих неопубликованных лекциях по теории групп 1909–1910 годов вновь представил графы Кэли под названием Gruppenbild (групповая диаграмма), что привело к современной геометрической теории групп. Его наиболее важным применением было решение проблемы слов для фундаментальной группы поверхностей . рода ≥ 2, что эквивалентно топологической проблеме определения того, какие замкнутые кривые на поверхности сжимаются в точку

См. также

• Вершинно-транзитивный граф
• Генераторная установка группы
• Гипотеза Ловаса
• Кубосвязные циклы
• Алгебраическая теория графов
• Граф цикла (алгебра)

Внешние ссылки

• Диаграммы Кэли
• Вайсштейн, Эрик В. «График Кэли» . Математический мир .