Cayleyův graf - Cayley graph

v matematika, a Cayleyův graf, také známý jako a Cayleyův barevný graf, Cayleyův diagram, skupinový diagramnebo barevná skupina[1] je graf který kóduje abstraktní strukturu a skupina. Jeho definici navrhuje Cayleyho věta (pojmenoval podle Arthur Cayley ) a používá specifikovaný, obvykle konečný, sada generátorů pro skupinu. Je to ústřední nástroj v kombinační a teorie geometrických skupin.
Definice
Předpokládejme to je skupina a je generující sada z . Cayleyův graf je barevný řízený graf konstruováno takto:[2]
- Každý prvek z je přiřazen vrchol: množina vrcholů z je identifikován s
- Každý generátor z je přiřazena barva .
- Pro všechny a vrcholy odpovídající prvkům a jsou spojeny směrovanou hranou barvy Tím se nastavila hrana sestává z dvojic formuláře s poskytnutí barvy.
v teorie geometrických skupin, sada obvykle se předpokládá, že je konečný, symetrický (tj. ) a neobsahující prvek identity skupiny. V tomto případě je nezbarvený Cayleyův graf obyčejný graf: jeho okraje nejsou orientovány a neobsahuje smyčky (jednoprvkové cykly).
Příklady
- Předpokládejme to je nekonečná cyklická skupina a množina se skládá ze standardního generátoru 1 a jeho inverze (−1 v aditivní notaci), pak je Cayleyův graf nekonečnou cestou.
- Podobně, pokud je konečný cyklická skupina řádu a sada se skládá ze dvou prvků, standardního generátoru a jeho inverzní, pak je Cayleyův graf cyklus . Obecněji řečeno, Cayleyovy grafy konečných cyklických skupin jsou přesně ty oběhové grafy.
- Cayleyův graf přímý součin skupin (s kartézský součin generujících sad jako generující sady) je kartézský součin odpovídajících Cayleyových grafů.[3] Tedy Cayleyův graf abelianské skupiny se sadou generátorů skládajících se ze čtyř prvků je nekonečný mřížka v letadle , zatímco pro přímý produkt s podobnými generátory je Cayleyův graf konečná mřížka na a torus.


- Cayleyův graf dihedrální skupina na dvou generátorech a je zobrazen vlevo. Červené šipky představují složení s . Od té doby je samo-inverzní, modré čáry, které představují složení s , jsou neorientovaní. Proto je graf smíšený: má osm vrcholů, osm šipek a čtyři hrany. The Cayleyho stůl skupiny lze odvodit z skupinová prezentace
- Jiný Cayleyův graf je zobrazen vpravo. je stále vodorovný odraz a je reprezentován modrými čarami a je diagonální odraz a je znázorněn růžovými čarami. Protože jsou oba odrazy samy inverzní, je Cayleyův graf vpravo zcela neorientovaný. Tento graf odpovídá prezentaci
- Cayleyův graf volná skupina na dvou generátorech a odpovídající sadě je zobrazen v horní části článku a představuje prvek identity. Cestování podél hrany doprava představuje správné násobení při cestování podél hrany nahoru odpovídá násobení Protože volná skupina nemá žádné vztahy, Cayleyův graf nemá cykly. Tento Cayleyův graf je 4pravidelný nekonečný strom a je klíčovou složkou důkazu o Banach – Tarski paradox.

- Cayleyův graf diskrétní Heisenbergova skupina
- je zobrazen vpravo. Generátory použité na obrázku jsou tři matice dané třemi permutacemi 1, 0, 0 pro položky . Uspokojují vztahy , což lze pochopit také z obrázku. Tohle je nekomutativní nekonečná skupina a přesto, že jde o trojrozměrný prostor, má Cayleyův graf čtyřrozměrný růst objemu.[Citace je zapotřebí ]
Charakterizace
Skupina činy na sobě levým násobením (viz Cayleyho věta ). To lze považovat za akci uživatele na jeho Cayleyově grafu. Výslovně prvek mapuje vrchol na vrchol Sada hran v Cayleyově grafu je zachována touto akcí: hrana se transformuje do okraje . Levá multiplikační akce jakékoli skupiny sama o sobě je jednoduše tranzitivní, zejména Cayleyův graf je vrchol tranzitivní. To vede k následující charakterizaci Cayleyových grafů:
- Sabidussiho věta. Graf je Cayleyův graf skupiny jen a jen tehdy, když připouští jednoduše přechodnou akci podle automatizmy grafů (tj. zachování sady hran).[4]
Obnovit skupinu a generátorovou soustavu z Cayleyova grafu vyberte vrchol a označte jej prvkem identity skupiny. Poté označte každý vrchol z jedinečným prvkem který se transformuje do Sada generátorů to přináší protože Cayleyův graf je sada popisků vrcholů sousedících s vybraným vrcholem. Generující množina je konečná (toto je běžný předpoklad pro Cayleyovy grafy) právě tehdy, když je graf lokálně konečný (tj. Každý vrchol sousedí s konečně mnoha hranami).
Základní vlastnosti
- Pokud je členem generující soustavy je její vlastní inverzní, pak je obvykle reprezentován neorientovanou hranou.
- Cayleyův graf zásadním způsobem závisí na výběru sady generátorů. Například pokud je generující sada má prvky pak má každý vrchol Cayleyova grafu příchozí a odchozí směrované hrany. V případě symetrické generující množiny s prvků, Cayleyův graf je a pravidelný směrovaný graf stupně
- Cykly (nebo uzavřené procházky) v Cayleyově grafu označte vztahy mezi prvky Ve složitější konstrukci Cayley komplex skupiny, uzavřené cesty odpovídající vztahům jsou „vyplněny“ pomocí mnohoúhelníky. To znamená, že problém konstrukce Cayleyova grafu dané prezentace je ekvivalentní řešení Slovní problém pro .[1]
- Li je surjektivní skupinový homomorfismus a obrazy prvků generující množiny pro jsou odlišné, pak to vyvolá pokrytí grafů
- kde Zejména pokud skupina má generátory, všechny se liší od 2, a sada se skládá z těchto generátorů spolu s jejich inverzemi, pak z Cayleyova grafu je pokryta nekonečným pravidelným strom stupně odpovídající volná skupina na stejné sadě generátorů.
- Graf lze postavit, i když je sada negeneruje skupinu Ale je odpojen a nepovažuje se za Cayleyův graf. V tomto případě každá připojená součást grafu představuje soubor podskupiny generované
- Pro jakýkoli konečný Cayleyův graf, považovaný za neorientovaný, se konektivita vrcholů je alespoň rovna 2/3 stupeň grafu. Pokud je generující množina minimální (odstranění libovolného prvku a pokud je jeho inverze z generující množiny ponechává množinu, která se negeneruje), je vrcholová konektivita rovna míře. The okrajová konektivita se ve všech případech rovná míře.[5]
- Každá skupina charakter skupiny vyvolává vlastní vektor z matice sousedství z . Když je Abelian, přidružený vlastní číslo je
- Zejména přidružené vlastní číslo triviálního znaku (ten, který posílá každý prvek na 1) je stupeň , to znamená v pořadí . Li je Abelianská skupina, existují přesně znaků, určující všechna vlastní čísla.
Schreierův cosetový graf
Pokud jeden místo toho vezme vrcholy jako pravé kosety pevné podskupiny jeden získá související konstrukci, Schreierův cosetový graf, který je základem coset výčet nebo Proces Todd – Coxeter.
Spojení s teorií skupin
Znalosti o struktuře skupiny lze získat studiem matice sousedství grafu a zejména použití vět o teorie spektrálních grafů.
The rod skupiny je minimální rod pro jakýkoli Cayleyův graf této skupiny.[6]
Teorie geometrických skupin
Pro nekonečné skupiny platí hrubá geometrie Cayleyova grafu je pro teorie geometrických skupin. Pro konečně generovaná skupina, toto je nezávislé na volbě konečné sady generátorů, tedy vnitřní vlastnost skupiny. To je zajímavé pouze pro nekonečné skupiny: každá konečná skupina je hrubě ekvivalentní bodu (nebo triviální skupině), protože lze zvolit jako konečnou množinu generátorů celou skupinu.
Formálně má pro daný výběr generátorů jeden slovo metrické (přirozená vzdálenost na Cayleyově grafu), která určuje a metrický prostor. Třída hrubé ekvivalence tohoto prostoru je invariantem skupiny.
Dějiny
Cayleyovy grafy byly nejprve zvažovány pro konečné skupiny od Arthur Cayley v roce 1878.[2] Max Dehn ve svých nepublikovaných přednáškách o teorii grup z let 1909–10 znovu zavedl Cayleyovy grafy pod názvem Gruppenbild (skupinový diagram), což vedlo k dnešní geometrické teorii grup. Jeho nejdůležitější aplikací bylo řešení slovní úloha pro základní skupina z povrchy s rodem ≥ 2, což odpovídá topologickému problému rozhodování o tom, které uzavřené křivky na povrchu se smršťují k bodu.[7]
Bethe mříž
The Bethe mříž nebo nekonečný strom Cayley je Cayleyův graf volné skupiny na generátory. Prezentace skupiny podle generátory odpovídá surjektivní mapě z volné skupiny na generátory do skupiny a na úrovni Cayleyových grafů na mapu od nekonečného stromu Cayley po Cayleyův graf. To lze také interpretovat (v algebraická topologie ) jako univerzální kryt Cayleyova grafu, což obecně není jednoduše připojeno.
Viz také
- Vrcholově přechodný graf
- Generující sada skupiny
- Lovász dohad
- Krychle spojené cykly
- Algebraická teorie grafů
- Cyklický graf (algebra)
Poznámky
- ^ A b Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (2004) [1966]. Kombinatorická teorie skupin: Prezentace skupin z hlediska generátorů a vztahů. Kurýr. ISBN 978-0-486-43830-6.
- ^ A b Cayley, Arthur (1878). „Desiderata a návrhy: Ne. 2. Teorie skupin: grafické znázornění“. American Journal of Mathematics. 1 (2): 174–6. doi:10.2307/2369306. JSTOR 2369306. Ve svých Shromážděných matematických dokumentech 10: 403–405.
- ^ Theron, Daniel Peter (1988), Rozšíření konceptu graficky pravidelných reprezentací, Ph.D. práce, University of Wisconsin, Madison, str. 46, PAN 2636729.
- ^ Sabidussi, Gert (Říjen 1958). „Ve třídě grafů bez pevného bodu“. Proceedings of the American Mathematical Society. 9 (5): 800–4. doi:10.1090 / s0002-9939-1958-0097068-7. JSTOR 2033090.
- ^ Viz věta 3.7 z Babai, László (1995). „Kapitola 27: Automorfické skupiny, izomorfismus, rekonstrukce“ (PDF). v Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.). Příručka kombinatoriky. Amsterdam: Elsevier. 1447–1540.
- ^ White, Arthur T. (1972). „Na rodu skupiny“. Transakce Americké matematické společnosti. 173: 203–214. doi:10.1090 / S0002-9947-1972-0317980-2. PAN 0317980.
- ^ Dehn, Max (2012) [1987]. Články o teorii skupiny a topologii. Springer-Verlag. ISBN 1461291070. Přeloženo z němčiny a s úvody a přílohou od John Stillwell, as dodatkem od Otto Schreier.