График Кэли - Cayley graph

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

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

Определение

Позвольте быть группой и быть порождающим набором из . Граф Кэли - это ориентированный граф с краской ребер, построенный следующим образом: ${\ 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 S = S ^ {- 1}}$

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

Примеры

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

Граф Кэли группы диэдра на двух образующих 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 \ 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

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

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

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

Чтобы восстановить группу и генераторную установку из немеченого ориентированного графа, выберите вершину и пометьте ее идентичным элементом группы. Затем маркировать каждую вершину из уникального элемента , который отображает до Множества генераторов , который дает как граф Кэлей является набором меток затраченных соседей . ${\ displaystyle G}$${\ displaystyle S}$${\ displaystyle \ Gamma,}$${\ Displaystyle v_ {1} \ в 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 (G, S)}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle S}$${\ displaystyle r}$${\ displaystyle r.}$
• Циклы (или замкнутые прогулки ) в графе Кэли указывают отношения между элементами. В более сложной конструкции комплекса Кэли группы замкнутые пути, соответствующие отношениям, «заполняются» многоугольниками . Это означает, что проблема построения графа Кэли данной презентации эквивалентна решению проблемы Word для .${\ 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 степени графа. Если порождающий набор минимален (удаление любого элемента и, если он присутствует, его обратный элемент из порождающего набора оставляет набор, который не порождает), связность вершин равна степени. Подключения краев во всех случаях равны степени.
• Каждая группа символы группы индуцирует собственный вектор из матрицы смежности из . Когда является абелевым, соответствующее собственное значение равно${\ displaystyle \ chi}$${\ displaystyle G}$${\ Displaystyle \ Gamma (G, S)}$${\ displaystyle G}$

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

В частности, соответствующее собственное значение тривиального символа (которое переводит каждый элемент в 1) является степенью , то есть порядком . Если - абелева группа, есть ровно символы, определяющие все собственные значения.${\ Displaystyle \ Gamma (G, S)}$${\ displaystyle S}$${\ displaystyle G}$${\ displaystyle | G |}$

Граф смежного класса Шрайера

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

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

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

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

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

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

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

История

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

Решетка Бете

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

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

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

Примечания

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

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