Граф Кэли

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

Граф Кэли свободной группы с двумя образующими 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}$

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

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

График Кэли 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 }$

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

Теорема Сабидусси  .  Ориентированный граф (немаркированный и неокрашенный) является графом Кэли группы тогда и только тогда, когда он допускает просто транзитивное действие автоморфизмов графа (т. е. сохраняет множество направленных ребер). ^[4] ${\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}}}$
• Если – гомоморфизм сюръективной группы и образы элементов порождающего множества для различны, то он индуцирует накрытие графов ${\displaystyle f:G'\to G}$ ${\displaystyle S'}$ ${\displaystyle G'}$
  $${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),}$$
  где, в частности, если группа имеет генераторы, все порядка отличного от 2, и множество состоит из этих генераторов вместе с их обратными, то граф Кэли покрывается бесконечным регулярным деревом степени , соответствующей свободной группе на том же самом набор генераторов. ${\displaystyle S=f(S').}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle \Gamma (G,S)}$ ${\displaystyle 2k}$
• Для любого конечного графа Кэли, рассматриваемого как неориентированный, связность вершин равна как минимум 2/3 степени графа . Если порождающий набор минимален (удаление любого элемента и, если он есть, обратного ему из порождающего набора, остается набор, который не является порождающим), связность вершин равна степени. Связность ребер во всех случаях равна степени. ^[5]
• Если – леворегулярное представление с обозначенной матричной формой , матрица смежности равна . ${\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)]}$
• Каждый групповой характер группы индуцирует собственный вектор матрицы смежности . Соответствующее собственное значение ${\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|}}$$
  для целых чисел В частности, соответствующее собственное значение тривиального символа (того, который переводит каждый элемент в 1) является степенью , то есть порядком . Если — абелева группа, то существуют ровно характеры, определяющие все собственные значения. Соответствующий ортонормированный базис собственных векторов имеет вид. Интересно отметить, что этот собственный базис не зависит от порождающего набора . ${\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).}$

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

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

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

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

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

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

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

Если дискретная группа обладает свойством Каждана (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 изоморфны , или для простых чисел . ^[8] Важно, чтобы на самом деле генерировалась вся группа , чтобы граф Кэли был связным. (Если не порождает , граф Кэли все еще может быть целым, но дополнение не обязательно является подгруппой.) ${\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}$

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

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

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

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

Полный список целых групп Кэли задается , а дициклическая группа порядка , где и – группа кватернионов. ^[8] Доказательство опирается на два важных свойства целочисленных групп Кэли: ${\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 году, доказывает, что граф Кэли является целым для любого эйлерова нормального подмножества , с использованием чисто теоретических методов представления. ^[9] ${\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, что эквивалентно топологической проблеме определения того, какие замкнутые кривые на поверхности сжимаются в точку . ^[10]

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

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

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]. Комбинаторная теория групп: представление групп через генераторы и отношения. Курьер. ISBN 978-0-486-43830-6.
2. Кэли, Артур (1878). «Пожелания и предложения: № 2. Теория групп: графическое изображение». Американский журнал математики . 1 (2): 174–6. дои : 10.2307/2369306. JSTOR  2369306.В его Сборнике математических статей 10: 403–405.
3. Терон, Дэниел Питер (1988), Расширение концепции графически регулярных представлений , доктор философии. диссертация, Университет Висконсина, Мэдисон, с. 46, МР  2636729.
4. Сабидусси, Герт (октябрь 1958 г.). «Об одном классе графов без неподвижных точек». Труды Американского математического общества . 9 (5): 800–4. дои : 10.1090/s0002-9939-1958-0097068-7 . JSTOR  2033090.
5. См. теорему 3.7 Бабая, Ласло (1995). «27. Группы автоморфизмов, изоморфизм, реконструкция» (PDF) . В Грэме, Рональд Л .; Гретшель, Мартин ; Ловас, Ласло (ред.). Справочник по комбинаторике. Том. 1. Эльзевир. стр. 1447–1540. ISBN 9780444823465.
6. Уайт, Артур Т. (1972). «О роде группы». Труды Американского математического общества . 173 : 203–214. дои : 10.1090/S0002-9947-1972-0317980-2 . МР  0317980.
7. Предложение 1.12 у Любоцкого, Александра (2012). «Расширенные графы в чистой и прикладной математике». Бюллетень Американского математического общества . 49 : 113–162. arXiv : 1105.2389 . дои : 10.1090/S0273-0979-2011-01359-3 .
8. Ахмади, Ажван; Белл, Джейсон; Мохар, Боян (2014). «Интегральные графы и группы Кэли». SIAM Journal по дискретной математике . 28 (2): 685–701. arXiv : 1307.6155 . дои : 10.1137/130925487. S2CID  207067134.
9. Го, В.; Лыткина Д.В.; Мазуров В.Д.; Ревин, DO (2019). «Интегральные графы Кэли» (PDF) . Алгебра и логика . 58 (4): 297–305. arXiv : 1808.01391 . дои : 10.1007/s10469-019-09550-2. S2CID  209936465.
10. Ден, Макс (2012) [1987]. Статьи по теории групп и топологии . Спрингер-Верлаг. ISBN 978-1461291077.Переведено с немецкого, с введениями и приложением Джона Стиллвелла , а также с приложением Отто Шрайера .

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

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