График Кэли

Граф, определенный из математической группы

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

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

Определение

Пусть будет группой и будет порождающим множеством . Граф Кэли — это ориентированный граф с рёберной раскраской , построенный следующим образом: ^[2] ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle \Gamma =\Gamma (G,S)}$

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

Не каждое соглашение требует, чтобы генерировалась группа. Если не является генерирующим набором для , то является несвязанным и каждый связанный компонент представляет смежный класс подгруппы, сгенерированной . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle \Gamma }$ ${\displaystyle S}$

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

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

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

Примеры

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

Граф Кэли диэдральной группы с двумя образующими a и b ${\displaystyle D_{4}}$

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

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

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

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

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

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

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

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

Теорема Сабидусси  —  (Непомеченный и неокрашенный) ориентированный граф является графом Кэли группы тогда и только тогда, когда он допускает простое транзитивное действие автоморфизмов графа ( т. е. сохранение множества ориентированных ребер). ^[5] ${\displaystyle \Gamma }$ ${\displaystyle G}$ ${\displaystyle G}$

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

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

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

Граф смежных классов Шрайера

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

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

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

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

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

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

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

Расширительные свойства

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

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

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

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

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

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

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

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

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

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

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

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

Интегральная группа Кэли

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

Полный список целочисленных групп Кэли задается как , и дициклическая группа порядка , где и — группа кватернионов. ^[9] Доказательство опирается на два важных свойства целочисленных групп Кэли: ${\displaystyle \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}}$ ${\displaystyle 12}$ ${\displaystyle m,n\in \mathbb {Z} _{\geq 0}}$ ${\displaystyle Q_{8}}$

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

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

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

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

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

История

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

Смотрите также

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

1. Доказательство: Пусть — произвольный автоморфизм цветного ориентированного графа , и пусть — образ тождества. Покажем, что для всех , индукцией по расстоянию между ребрами от . Предположим . Автоморфизм переводит любое -цветное ребро в другое -цветное ребро . Следовательно , ​​и индукция продолжается. Поскольку связно, это показывает для всех . ${\displaystyle \sigma :V(\Gamma )\to V(\Gamma )}$ ${\displaystyle \Gamma }$ ${\displaystyle h=\sigma (e)}$ ${\displaystyle \sigma (g)=hg}$ ${\displaystyle g\in V(\Gamma )}$ ${\displaystyle g}$ ${\displaystyle e}$ ${\displaystyle \sigma (g)=hg}$ ${\displaystyle \sigma }$ ${\displaystyle c_{s}}$ ${\displaystyle g\to gs}$ ${\displaystyle c_{s}}$ ${\displaystyle \sigma (g)\to \sigma (gs)}$ ${\displaystyle \sigma (gs)=\sigma (g)s=hgs}$ ${\displaystyle \Gamma }$ ${\displaystyle \sigma (g)=hg}$ ${\displaystyle g\in V(\Gamma )}$
2. Его легко преобразовать в простой граф (неокрашенный, неориентированный), группа симметрии которого изоморфна : заменить окрашенные направленные ребра подходящими деревьями, соответствующими цветам. ${\displaystyle \Gamma }$ ${\displaystyle G}$ ${\displaystyle \Gamma }$

Примечания

1. Магнус, Вильгельм ; Каррасс, Абрахам; Солитэр, Дональд (2004) [1966]. Комбинаторная теория групп: представления групп в терминах генераторов и отношений. Courier. ISBN 978-0-486-43830-6.
2. Cayley, Arthur (1878). «Desiderata and suggestions: No. 2. The Theory of groups: graphical representation». American Journal of Mathematics . 1 (2): 174–6. doi :10.2307/2369306. JSTOR  2369306.В его Сборнике математических трудов 10: 403–405.
3. Терон, Дэниел Питер (1988). Расширение концепции графически регулярных представлений (диссертация доктора философии). Университет Висконсина, Мэдисон. стр. 46. MR  2636729..
4. Bartholdi, Laurent (2017). "Рост групп и сплетенных произведений". В Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (ред.). Группы, графы и случайные блуждания: избранные статьи с семинара, состоявшегося в Кортоне 2–6 июня 2014 г. London Math. Soc. Lecture Note Ser. Vol. 436. Cambridge Univ. Press, Cambridge. pp. 1–76. arXiv : 1512.07044 . ISBN 978-1-316-60440-3. МР  3644003.
5. Sabidussi, Gert (октябрь 1958). «О классе графов без фиксированных точек». Труды Американского математического общества . 9 (5): 800–4. doi : 10.1090/s0002-9939-1958-0097068-7 . JSTOR  2033090.
6. См. теорему 3.7 Бабая, Ласло (1995). «27. Группы автоморфизмов, изоморфизм, реконструкция» (PDF) . В Грэме, Рональд Л .; Гретшель, Мартин ; Ловас, Ласло (ред.). Справочник по комбинаторике. Том. 1. Эльзевир. стр. 1447–1540. ISBN 9780444823465.
7. Уайт, Артур Т. (1972). «О роде группы». Труды Американского математического общества . 173 : 203–214. doi : 10.1090/S0002-9947-1972-0317980-2 . MR  0317980.
8. Предложение 1.12 в Lubotzky, Alexander (2012). «Расширительные графы в чистой и прикладной математике». Бюллетень Американского математического общества . 49 : 113–162. arXiv : 1105.2389 . doi : 10.1090/S0273-0979-2011-01359-3 .
9. Ahmady, Azhvan; Bell, Jason; Mohar, Bojan (2014). «Integral Cayley graphs and groups». SIAM Journal on Discrete Mathematics . 28 (2): 685–701. arXiv : 1307.6155 . doi : 10.1137/130925487. S2CID  207067134.
10. Го, В.; Лыткина Д.В.; Мазуров В.Д.; Ревин, DO (2019). «Интегральные графы Кэли» (PDF) . Алгебра и логика . 58 (4): 297–305. arXiv : 1808.01391 . дои : 10.1007/s10469-019-09550-2. S2CID  209936465.
11. Dehn, Max (2012) [1987]. Статьи по теории групп и топологии . Springer-Verlag. ISBN 978-1461291077.Перевод с немецкого языка с введением и приложением Джона Стиллвелла , а также с приложением Отто Шрайера .

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

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