Граф Кэли

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

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

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

Определение [ править ]

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

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

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

Примеры [ править ]

Предположим, что это бесконечная циклическая группа, и набор состоит из стандартной образующей 1 и ее обратной (−1 в аддитивной записи), тогда граф Кэли представляет собой бесконечный путь. ${\ Displaystyle G = \ mathbb {Z}}$ ${\ displaystyle S}$
Аналогично, если - конечная циклическая группа порядка и множество состоит из двух элементов, стандартного генератора и его обратного, то граф Кэли является циклом . В более общем смысле графы Кэли конечных циклических групп - это в точности циркулянтные графы . ${\ Displaystyle G = \ mathbb {Z} _ {п}}$ ${\ 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}}$ $n\times m$

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

D_{4}

Граф Кэли на двух самообратимых генераторах

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 .

Граф Кэли свободной группы на двух генераторов и соответствующий набор изображен в верхней части статьи, и представляет собой единичный элемент . Перемещение по ребру вправо представляет собой умножение вправо на, а перемещение по ребру вверх соответствует умножению на. Поскольку свободная группа не имеет отношений , граф Кэли не имеет циклов . Этот граф Кэли является 4- регулярным бесконечным деревом и является ключевым элементом доказательства парадокса Банаха – Тарского . $a$ $b$ $S=\{a,b,a^{-1},b^{-1}\}$ $e$ $a,$ $b.$

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

Граф Кэли дискретной группы Гейзенберга

\left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}

изображен справа. Генераторы, используемые на рисунке, представляют собой три матрицы, заданные тремя перестановками 1, 0, 0 для элементов . Они удовлетворяют отношениям , что тоже можно понять по картинке. Это некоммутативная бесконечная группа, и, несмотря на то, что он является трехмерным пространством, граф Кэли имеет четырехмерный рост объема . ^[^{необходима цитата}^]

X,Y,Z

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)$

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

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

Элементарные свойства [ править ]

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

Граф Кэли существенно зависит от выбора набора образующих. Например, если в порождающем множестве есть элементы, то каждая вершина графа Кэли имеет входящие и исходящие направленные ребра. В случае симметричного порождающего множества с элементами граф Кэли является регулярным ориентированным графом степени $\Gamma (G,S)$ $S$ $S$ $k$ $k$ $k$ $S$ $r$ $r.$

Циклы (или замкнутые прогулки ) в графе Кэли указывают на отношения между элементами. В более сложной конструкции комплекса Кэли группы замкнутые пути, соответствующие отношениям, «заполняются» многоугольниками . Это означает, что задача построения графа Кэли данной презентации эквивалентна решению проблемы Word для . ^[1] $S.$ ${\mathcal {P}}$ ${\mathcal {P}}$

Если - гомоморфизм сюръективной группы и образы элементов порождающего множества для различны, то он индуцирует покрытие графов $f:G'\to G$ $S'$ $G'$

{\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),

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

S=f(S').

G

k

S

\Gamma (G,S)

2k

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

Для любого конечного графа Кэли, рассматриваемого как неориентированный, связность вершин равна по крайней мере 2/3 степени графа. Если порождающий набор минимален (удаление любого элемента и, если он присутствует, его обратный элемент из порождающего набора оставляет набор, который не порождает), связность вершин равна степени. Подключения краев во всех случаях равны степени. ^[5]

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

\lambda _{\chi }=\sum _{s\in S}\chi (s).

В частности, соответствующее собственное значение тривиального символа (которое переводит каждый элемент в 1) является степенью , то есть порядком . Если - абелева группа, есть ровно символы, определяющие все собственные значения.

\Gamma (G,S)

S

G

|G|

График смежности Шрайера [ править ]

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

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

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

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

Геометрическая теория групп [ править ]

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

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

История [ править ]

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

Решетка Бете [ править ]

Решетки Бете или бесконечное дерево Кэли является граф Кэли свободной группы генераторов. Представление группы по генераторам соответствуют к сюръективной карте от свободной группы генераторов в группу , так и на уровне графов Кэлей на карту от бесконечного Кэли дерева на графу Кэлей. Это также можно интерпретировать (в алгебраической топологии ) как универсальное покрытие графа Кэли, которое в общем случае не является односвязным . $n$ $G$ $n$ $n$ $G,$

См. Также [ править ]

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

Заметки [ править ]

^ а б Магнус, Вильгельм ; Каррасс, Авраам; Солитэр, Дональд (2004) [1966]. Комбинаторная теория групп: представления групп в терминах генераторов и отношений . Курьер. ISBN 978-0-486-43830-6.
^ a b Кэли, Артур (1878). «Дезидерата и предложения: № 2. Теория групп: графическое представление» . Американский журнал математики . 1 (2): 174–6. DOI : 10.2307 / 2369306 . JSTOR 2369306 . В его «Сборнике математических статей» 10: 403–405.
^ Терон, Дэниел Питер (1988), Расширение концепции графически регулярных представлений , доктор философии. диссертация, Университет Висконсина, Мэдисон, стр. 46, Руководство по ремонту 2636729 .
^ Сабидусси Герт (октябрь 1958). «Об одном классе графов без неподвижных точек» . Труды Американского математического общества . 9 (5): 800–4. DOI : 10.1090 / s0002-9939-1958-0097068-7 . JSTOR 2033090 .
^ См. Теорему 3.7 Бабая, Ласло (1995). «Глава 27: Группы автоморфизмов, изоморфизм, реконструкция» (PDF) . У Грэма, Рональда Л .; Грёчель, Мартин ; Ловас, Ласло (ред.). Справочник по комбинаторике . Амстердам: Эльзевир. С. 1447–1540.
^ Уайт, Артур Т. (1972). «О роде группы» . Труды Американского математического общества . 173 : 203–214. DOI : 10.1090 / S0002-9947-1972-0317980-2 . Руководство по ремонту 0317980 .
^ Ден, Макс (2012) [1987]. Работы по теории групп и топологии . Springer-Verlag. ISBN 1461291070.Переведено с немецкого, с введением и приложением Джона Стилвелла и с приложением Отто Шрайера .

Внешние ссылки [ править ]

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

[CGT-1] а б Магнус, Вильгельм ; Каррасс, Авраам; Солитэр, Дональд (2004) [1966]. Комбинаторная теория групп: представления групп в терминах генераторов и отношений . Курьер. ISBN 978-0-486-43830-6.

[Cayley78-2] Кэли, Артур (1878). «Дезидерата и предложения: № 2. Теория групп: графическое представление» . Американский журнал математики . 1 (2): 174–6. DOI : 10.2307 / 2369306 . JSTOR 2369306 . В его «Сборнике математических статей» 10: 403–405.

[3] Терон, Дэниел Питер (1988), Расширение концепции графически регулярных представлений , доктор философии. диссертация, Университет Висконсина, Мэдисон, стр. 46, Руководство по ремонту 2636729 .

[4] Сабидусси Герт (октябрь 1958). «Об одном классе графов без неподвижных точек» . Труды Американского математического общества . 9 (5): 800–4. DOI : 10.1090 / s0002-9939-1958-0097068-7 . JSTOR 2033090 .

[5] См. Теорему 3.7 Бабая, Ласло (1995). «Глава 27: Группы автоморфизмов, изоморфизм, реконструкция» (PDF) . У Грэма, Рональда Л .; Грёчель, Мартин ; Ловас, Ласло (ред.). Справочник по комбинаторике . Амстердам: Эльзевир. С. 1447–1540.

[6] Уайт, Артур Т. (1972). «О роде группы» . Труды Американского математического общества . 173 : 203–214. DOI : 10.1090 / S0002-9947-1972-0317980-2 . Руководство по ремонту 0317980 .

[7] Ден, Макс (2012) [1987]. Работы по теории групп и топологии . Springer-Verlag. ISBN 1461291070.Переведено с немецкого, с введением и приложением Джона Стилвелла и с приложением Отто Шрайера .

[1]