Graficul lui Cayley

În matematică , un grafic Cayley (numit după Arthur Cayley ) este un grafic care codifică structura unui grup . Este un instrument important pentru studiul combinatoriei și geometria grupurilor .

Definiție

Familii de grafice definite de automorfismele lor
la distanță tranzitivă	→	distanță regulată	←	puternic regulat
↓
simetric (arc tranzitiv)	←	t- tranzitiv, ( t  ≥ 2)		stânga simetrică  (în)
↓
(dacă este conectat) vârf tranzitiv și margine tranzitiv	→	regulat și tranzitiv de margine	→	marginea-tranzitivă
↓		↓		↓
top-tranzitiv	→	regulat	→	(dacă este bipartit) biregular
↑
Grafic Cayley	←	zero-simetric		asimetric

Având în vedere un grup și o parte generatoare a acestui grup, graficul lui Cayley Cay (G, S) este construit după cum urmează: (G,∗){\ displaystyle (G, *)} S{\ displaystyle S}

• Fiecărui element al , îi asociem un vârf .g{\ displaystyle g}G{\ displaystyle G}vg{\ displaystyle v_ {g}}
• Fiecare element al , asociem o culoare .s{\ displaystyle s}S{\ displaystyle S}vs.s{\ displaystyle c_ {s}}
• Pentru toate și , desenăm o margine de culoare orientată de sus în sus .g∈G{\ displaystyle g \ în G}s∈S{\ displaystyle s \ în S}vs.s{\ displaystyle c_ {s}}vg{\ displaystyle v_ {g}}vg∗s{\ displaystyle v_ {g * s}}

De asemenea, putem asocia fiecare generator cu o direcție mai degrabă decât cu o culoare, dar este uneori imposibil să se reprezinte graficul în plan. În unele contexte, folosim înmulțirea cu mâna stângă mai degrabă decât cu mâna dreaptă (muchiile merg de la la ). vg{\ displaystyle v_ {g}}vs∗g{\ displaystyle v_ {s * g}}

Proprietăți

• Deoarece setul generator al unui grup nu este unic, structura graficelor Cayley a unui grup dat nu este unică.
• Dacă grupul generator are elemente, fiecare vârf are margini de intrare și margini de ieșire.nu{\ displaystyle n}nu{\ displaystyle n}nu{\ displaystyle n}
• Ciclurile graficului corespund relațiilor verificate de generatoare.
• Dacă și sunt ambele în grupul generatorului, înlocuim adesea fiecare pereche de muchii orientate corespunzătoare și cu o singură margine neorientată.s{\ displaystyle s}s-1{\ displaystyle s ^ {- 1}}s{\ displaystyle s}s-1{\ displaystyle s ^ {- 1}}

Exemple

Graficul Cayley al grupului gratuit cu două generatoare este afișat în partea dreaptă sus a paginii. ( este elementul neutru). Un pas spre dreapta corespunde unei înmulțiri cu , la stânga cu , în sus cu și în jos. Deoarece nu există relații în grupul liber (prin definiție), graficul său Cayley este aciclic. e{\ displaystyle e}la{\ displaystyle a}la-1{\ displaystyle a ^ {- 1}}b{\ displaystyle b}b-1{\ displaystyle b ^ {- 1}}

În dreapta este un desen al graficului Cayley al unui grup de ordine 18 cu prezentare . Este generat de trei elemente de ordinul 2, care sunt, prin urmare, reprezentate de margini neorientate de trei culori diferite; fiecare vârf este legat de o margine a fiecărei culori. Urmărind marginile putem verifica dacă celelalte relații sunt satisfăcute. Dacă, de exemplu, pentru generatoarele x , y și z alegem respectiv culorile roșu, verde și albastru (dar nu contează, prezentarea este perfect simetrică), vedem că, pornind de la orice vârf, secvența roșu-verde-roșu-verde-roșu-verde ne readuce la punctul nostru de plecare (atunci ( xy ) 3 = 1), precum și secvența roșu-verde-albastru-roșu-verde-albastru (apoi ( xyz ) 2 = 1). <X,y,z|X2=y2=z2=(Xy)3=(Xz)3=(yz)3=(Xyz)2=1>{\ displaystyle <x, y, z | x ^ {2} = y ^ {2} = z ^ {2} = (xy) ^ {3} = (xz) ^ {3} = (yz) ^ {3 } = (xyz) ^ {2} = 1>}

Vezi și tu

Articol asociat

Metrică a cuvintelor

Link extern

(ro) Eric W. Weisstein , „  Cayley Graph  ” , pe MathWorld

Bibliografie

• (ro) Arthur Cayley , „  Despre teoria grupurilor  ” , Proc. London Math. Soc. , n o  9,1878, p.  126-133
• (ro) HSM Coxeter și WOJ Moser  (de) , Generatori și relații pentru grupuri discrete , Springer ,1972( Repr.  2013), 3 e  ed. ( 1 st  ed. 1957), 164  p. ( ISBN  978-3-662-21946-1 , prezentare online ) , „3. Grafice, hărți și diagrame Cayley” , p.  18-32.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">