Il grafico di Cayley

In matematica , un grafico di Cayley (dal nome di Arthur Cayley ) è un grafico che codifica la struttura di un gruppo . È uno strumento importante per lo studio della combinatoria e della geometria dei gruppi .

Definizione

Famiglie di grafici definiti dai loro automorfismi
distanza transitiva	→	distanza regolare	←	fortemente regolare
↓
simmetrico (arco transitivo)	←	t -transitivo, $( t \geq 2)$		simmetrico a sinistra (in)
↓
(se connesso) vertex-transitive e edge-transitive	→	regolare e transitivo di bordo	→	edge-transitive
↓		↓		↓
top-transitivo	→	regolare	→	(se bipartito) biregolare
↑
Grafico di Cayley	←	zero simmetrico		asimmetrico

Dato un gruppo e una parte generatrice di questo gruppo, il grafico di Cayley Cay (G, S) è costruito come segue: $(G, *)$ $S$

Associamo un vertice a ogni elemento di . $g$ $G$ $v_ {g}$
Ad ogni elemento di , associamo un colore . $S$ $S$ $c_ {s}$
Per tutti e , disegniamo un bordo colorato orientato dall'alto verso l'alto . $g \ in G$ $s \ in S$ $c_ {s}$ $v_ {g}$ ${\ displaystyle v_ {g * s}}$

Possiamo anche associare a ciascun generatore una direzione piuttosto che un colore, ma a volte è impossibile rappresentare il grafico nel piano. In alcuni contesti, usiamo la moltiplicazione per la mano sinistra piuttosto che per la mano destra (gli archi vanno da a ). $v_ {g}$ ${\ displaystyle v_ {s * g}}$

Proprietà

Poiché il gruppo elettrogeno di un gruppo non è unico, la struttura dei grafici di Cayley di un dato gruppo non è unica.
Se il gruppo elettrogeno ha elementi, ogni vertice ha bordi in entrata e bordi in uscita. $non$ $non$ $non$
I cicli del grafico corrispondono alle relazioni verificate dai generatori.
Se e sono entrambi nel gruppo elettrogeno, spesso sostituire ogni coppia di bordi orientati corrispondenti ad e da un singolo bordo non orientato. $S$ $s ^ {- 1}$ $S$ $s ^ {- 1}$

Esempi

Il grafico Cayley del gruppo libero con due generatori è mostrato in alto a destra nella pagina. ( è l'elemento neutro). Un passo a destra corrisponde a una moltiplicazione per , a sinistra per , su e giù. Poiché non ci sono relazioni nel gruppo libero (per definizione), il suo grafo di Cayley è aciclico. $e$ $a$ $a ^ {{- 1}}$ $b$ $b ^ {- 1}$

A destra c'è un disegno del grafico di Cayley di un gruppo di ordine 18 con presentazione . È generato da tre elementi di ordine 2, che sono quindi rappresentati da bordi non orientati di tre diversi colori; ogni vertice è collegato a un bordo di ogni colore. Seguendo i bordi possiamo verificare che le altre relazioni sono soddisfatte. Se, per esempio, per i generatori x , y , e z abbiamo scelto rispettivamente i colori rosso, verde e blu (ma non importa, la presentazione è perfettamente simmetrica), vediamo che, partendo da un qualsiasi vertice, la la sequenza rosso-verde-rosso-verde-rosso-verde ci riporta al nostro punto di partenza (quindi ( xy ) 3 = 1), e anche la sequenza rosso-verde-blu-rosso-verde-blu (quindi ( xyz ) 2 = 1). $<x, y, z | x ^ 2 = y ^ 2 = z ^ 2 = (xy) ^ 3 = (xz) ^ 3 = (yz) ^ 3 = (xyz) ^ 2 = 1>$

Vedi anche

Articolo correlato

Metrica delle parole

Link esterno

(it) Eric W. Weisstein , " Cayley Graph " , su MathWorld

Bibliografia

(it) Arthur Cayley , " Sulla teoria dei gruppi " , Proc. London Math. Soc. , n o 9,1878, p. 126-133
(en) HSM Coxeter e WOJ Moser (de) , Generators and Relations for Discrete Groups , Springer ,1972( Repr.2013 ), 3 e ed. ( 1 ° ed. 1957), 164 p. ( ISBN 978-3-662-21946-1 , presentazione in linea ) , "3. Grafici, mappe e diagrammi di Cayley" , p. 18-32.