Wykres Cayleya - Cayley graph

Wykres Cayleya wolnej grupy na dwóch generatorach a i b
Rodziny grafów definiowane przez ich automorfizmy
odległość przechodnia odległość-regularna mocno regularne
symetryczny (przechodni łukowo) t -przechodni, t  ≥ 2 skośno-symetryczny
(jeśli połączone)
wierzchołki i krawędzie przechodnie
krawędź przechodnia i regularna krawędź przechodnia
wierzchołek-przechodni regularny (jeśli dwustronna)
biregular
Wykres Cayleya zero-symetryczne asymetryczny

W matematyce , A wykres Cayley , znany także jako wykres Cayley koloru , Cayley schemacie , schemat grupa lub grupy koloru jest wykresem , który koduje streszczenie strukturę grupy . Jego definicję sugeruje twierdzenie Cayleya (nazwane tak od Arthura Cayleya ) i wykorzystuje określony zestaw generatorów dla grupy. Jest głównym narzędziem w kombinatorycznej i geometrycznej teorii grup .

Definicja

Pozwolić być grupy i być zespół prądotwórczy z . Wykres Cayleya jest grafem skierowanym w kolorze krawędzi, skonstruowanym w następujący sposób:

  • Każdy element z przypisany jest wierzchołek: zbiór wierzchołek jest identyfikowany z
  • Każdy element z przypisany jest kolor .
  • Dla każdego i istnieje skierowana krawędź koloru od wierzchołka odpowiadającego do odpowiadającego .

Nie każde źródło wymaga wygenerowania grupy. Jeśli nie jest zbiorem generującym dla , to jest odłączony i każdy połączony komponent reprezentuje zbiór podgrupy generowanej przez .

Jeżeli element z jego własny odwrotny, to jest zwykle reprezentowane przez nieukierunkowane krawędzi.

Czasami zakłada się, że zbiór jest symetryczny (tj. ) i nie zawiera elementu tożsamości grupy. W tym przypadku niepokolorowany graf Cayleya można przedstawić jako prosty graf nieskierowany .

W geometrycznej teorii grup często zakłada się , że zbiór jest skończony, co odpowiada temu, że jest lokalnie skończony.

Przykłady

  • Załóżmy, że jest to nieskończona grupa cykliczna, a zbiór składa się ze standardowego generatora 1 i jego odwrotności (-1 w notacji addytywnej); wtedy wykres Cayleya jest nieskończoną ścieżką.
  • Podobnie, jeśli jest to skończona cykliczna grupa porządku, a zbiór składa się z dwóch elementów, standardowego generatora i jego odwrotności, to graf Cayleya jest cyklem . Bardziej ogólnie, wykresy Cayley'a dla skończonych grup cyklicznych są dokładnie wykresami cyrkulacyjnymi .
  • Wykres Cayleya bezpośredniego iloczynu grup (z kartezjańskim iloczynem zbiorów generujących jako zbiorem generującym) jest iloczynem kartezjańskim odpowiednich grafów Cayleya. Zatem graf Cayleya grupy abelowej ze zbiorem generatorów składających się z czterech elementów jest nieskończoną siatką na płaszczyźnie , podczas gdy dla iloczynu bezpośredniego z podobnymi generatorami graf Cayleya jest skończoną siatką na torusie .
Wykres Cayleya grupy dwuściennej na dwóch generatorach a i b
Wykres Cayleya , na dwóch generatorach, które są samoodwrotne
  • Wykres Cayleya grupy dwuściennej na dwóch generatorach i jest przedstawiony po lewej stronie. Czerwone strzałki reprezentują kompozycję z . Ponieważ jest samoodwrotny , niebieskie linie reprezentujące kompozycję z , są nieskierowane. Dlatego wykres jest mieszany: ma osiem wierzchołków, osiem strzałek i cztery krawędzie. Cayley tabela grupy mogą pochodzić z prezentacji grupy
Po prawej stronie pokazano inny wykres Cayleya . jest nadal odbiciem poziomym i jest reprezentowane przez niebieskie linie i jest odbiciem ukośnym i jest reprezentowane przez linie różowe. Ponieważ oba odbicia są samoodwrotne, wykres Cayleya po prawej stronie jest całkowicie nieskierowany. Ten wykres odpowiada prezentacji
  • Wykres Cayleya wolnej grupy na dwóch generatorach i odpowiadający zbiorowi jest przedstawiony na górze artykułu i reprezentuje element tożsamości . Przemieszczanie się wzdłuż krawędzi w prawo reprezentuje prawe mnożenie przez, podczas gdy podróżowanie wzdłuż krawędzi w górę odpowiada mnożeniu przez Ponieważ wolna grupa nie ma relacji , graf Cayleya nie ma cykli . Ten wykres Cayleya jest 4- regularnym nieskończonym drzewem i jest kluczowym składnikiem dowodu paradoksu Banacha-Tarskiego .
Część wykresu Cayleya grupy Heisenberga. (Kolorowanie służy tylko jako pomoc wizualna.)
jest przedstawiony po prawej stronie. Generatory użyte na rysunku to trzy macierze podane przez trzy permutacje 1, 0, 0 dla wpisów . Spełniają relacje , co można również zrozumieć z obrazu. Jest to nieprzemienna grupa nieskończona i pomimo tego, że jest trójwymiarową przestrzenią, wykres Cayleya ma czterowymiarowy wzrost objętości .
Wykres Cayley Q8 przedstawiający cykle mnożenia przez kwaterniony i , j oraz k

Charakteryzacja

Grupa działa na siebie przez mnożenie od lewej (patrz twierdzenie Cayleya ). Może to być postrzegane jako działanie na jego wykresie Cayleya. Jawnie, element odwzorowuje wierzchołek na wierzchołek Zbiór krawędzi grafu Cayleya i ich kolor jest zachowywany dzięki tej akcji: krawędź jest odwzorowywana na edge , przy czym oba mają kolor . Lewe działanie mnożenia grupy na sobie jest po prostu przechodnie , w szczególności wykresy Cayleya są wierzchołkami przechodnie . Oto rodzaj odwrotności do tego:

Twierdzenie Sabidussiego. An (nieznakowanego i bezbarwny) skierowane wykres wykres Cayley grupy , wtedy i tylko wtedy, gdy przyjmuje się tylko działanie przechodni przez automorfizmy wykresu (czyli zachowanie zestaw skierowanych krawędziach) .

Aby odzyskać grupę i zestaw generujący z nieoznakowanego grafu skierowanego, wybierz wierzchołek i oznacz go elementem tożsamości grupy. Następnie oznaczyć każdy wierzchołek z przez unikalny element , który mapuje do The zestaw generatorów że plony jak wykres Cayley jest zbiorem etykiet poza sąsiadów .

Podstawowe właściwości

  • Wykres Cayleya w istotny sposób zależy od doboru zestawu generatorów. Na przykład, jeśli zbiór generujący zawiera elementy, to każdy wierzchołek grafu Cayleya ma skierowane krawędzie przychodzące i wychodzące. W przypadku symetrycznego zbioru generującego z elementami graf Cayleya jest regularnym grafem skierowanym stopnia
  • Cykle (lub spacery zamknięte ) na wykresie Cayleya wskazują relacje między elementami grupy. W bardziej rozbudowanej konstrukcji kompleksu Cayleya grupy ścieżki zamknięte odpowiadające relacjom są „wypełniane” wielokątami . Oznacza to, że zadanie skonstruowania wykresu Cayleya dla danej prezentacji jest równoważne rozwiązaniu Problemu Word dla .
  • Jeżeli jest surjektywnym homomorfizmem grupowym i obrazy elementów zbioru generującego dla są różne, to powoduje to pokrycie grafów
gdzie W szczególności, jeśli grupa ma generatory, wszystkie rzędu innego niż 2, a zbiór składa się z tych generatorów wraz z ich odwrotnościami, to graf Cayleya jest pokryty nieskończonym drzewem regularnym stopnia odpowiadającym wolnej grupie na tej samej zestaw generatorów.
  • Dla dowolnego skończonego grafu Cayleya, uważanego za nieskierowany, łączność wierzchołków jest co najmniej równa 2/3 stopnia grafu. Jeśli zespół generujący jest minimalny (usunięcie dowolnego elementu i, jeśli jest obecny, jego odwrotność z zespołu generującego pozostawia zespół, który nie generuje), łączność wierzchołków jest równa stopniowi. Łączność krawędź jest we wszystkich przypadkach równy stopień.
  • Każda grupa charakter grupy wywołuje wektor własny o macierz sąsiedztwa z . Kiedy jest abelian, skojarzona wartość własna to
W szczególności powiązana wartość własna trywialnego znaku (tego, który wysyła każdy element do 1) to stopień , czyli rząd . Jeśli jest grupą abelową, to są dokładnie znaki określające wszystkie wartości własne.

Wykres Schreiera Coset

Jeśli zamiast tego przyjmiemy wierzchołki jako prawe cosety ustalonej podgrupy, otrzymamy pokrewną konstrukcję, graf Schreiera coset , który jest podstawą wyliczenia cosetów lub procesu Todda-Coxetera .

Połączenie z teorią grup

Wiedzę o budowie grupy można uzyskać badając macierz sąsiedztwa grafu, aw szczególności stosując twierdzenia spektralnej teorii grafów .

Rodzaju grupy jest minimalna rodzaju dla każdego wykresu Cayley tej grupy.

Geometryczna teoria grup

W przypadku grup nieskończonych, zgrubna geometria grafu Cayleya ma fundamentalne znaczenie dla geometrycznej teorii grup . Dla skończenie generowanej grupy , jest to niezależne od wyboru skończonego zbioru generatorów, stąd wewnętrzna właściwość grupy. Jest to interesujące tylko dla grup nieskończonych: każda skończona grupa jest zgrubnie równoważna punktowi (lub grupie trywialnej), ponieważ jako skończony zbiór generatorów można wybrać całą grupę.

Formalnie dla danego wyboru generatorów mamy słowo metryka (naturalna odległość na wykresie Cayleya), które określa przestrzeń metryczną . Zgrubna klasa równoważności tej przestrzeni jest niezmiennikiem grupy.

Historia

Grafy Cayleya zostały po raz pierwszy rozważone dla grup skończonych przez Arthura Cayleya w 1878 roku. Max Dehn w swoich niepublikowanych wykładach z teorii grup z lat 1909-10 ponownie wprowadził grafy Cayleya pod nazwą Gruppenbild (diagram grupowy), co doprowadziło do dzisiejszej geometrycznej teorii grup. Jego najważniejsze zastosowanie było rozwiązanie problemu słowo dla podstawowej grupy o powierzchni z rodzaju równe 2, co jest równoważne topologicznej problemu zdecydowania których krzywe zamknięte w umowie powierzchni do punktu.

Bethe krata

Kratownica Bethe lub nieskończony Cayley drzewo jest wykres Cayley wolnej grupy o generatorów. Przedstawienie grupy przez generatory odpowiada surjektywnemu odwzorowaniu z wolnej grupy na generatory do grupy, a na poziomie grafów Cayleya odwzorowaniu z nieskończonego drzewa Cayleya na graf Cayleya. Można to również zinterpretować (w topologii algebraicznej ) jako uniwersalną osłonę grafu Cayleya, który nie jest na ogół po prostu połączony .

Zobacz też

Uwagi

Zewnętrzne linki